39. 组合总和

今天药忘吃喽~ 2022-09-10 12:19 135阅读 0赞

[https://leetcode-cn.com/problems/combination-sum/][https_leetcode-cn.com_problems_combination-sum]

难度中等1514收藏分享切换为英文接收动态反馈

给定一个**无重复元素**的正整数数组 `candidates` 和一个正整数 `target` ，找出 `candidates` 中所有可以使数字和为目标数 `target` 的唯一组合。

`candidates` 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。

对于给定的输入，保证和为 `target` 的唯一组合数少于 `150` 个。

**示例 1：**

输入: candidates = [2,3,6,7], target = 7
    输出: [[7],[2,2,3]]

**示例 2：**

输入: candidates = [2,3,5], target = 8
    输出: [[2,2,2,2],[2,3,3],[3,5]]

**示例 3：**

输入: candidates = [2], target = 1
    输出: []

**示例 4：**

输入: candidates = [1], target = 1
    输出: [[1]]

**示例 5：**

输入: candidates = [1], target = 2
    输出: [[1,1]]

**提示：**

*  `1 <= candidates.length <= 30`
 *  `1 <= candidates[i] <= 200`
 *  `candidate` 中的每个元素都是独一无二的。
 *  `1 <= target <= 500`

通过次数323,736提交次数445,190

class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            List<List<Integer>> ans = new ArrayList<List<Integer>>();
            List<Integer> combine = new ArrayList<Integer>();
            dfs(candidates,target,ans,combine,0);
            return ans;
        }
    
        public void dfs(int[] candidates,int target,List<List<Integer>> ans,List<Integer> combine,int idx)
        {
            if(idx == candidates.length)
            {
                return;
            }
    
            if(target ==0 )
            {
                ans.add(new ArrayList<Integer>(combine));
                return;
            }
            dfs(candidates,target,ans,combine,idx+1);
    
            if(target -candidates[idx] >= 0)
            {
                combine.add(candidates[idx]);
                dfs(candidates,target -candidates[idx],ans,combine,idx);
                combine.remove(combine.size()-1);
            }
        }
    }

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5Yqq5Yqb5a2m5Lmg55qE5qKF5a2Q_size_19_color_FFFFFF_t_70_g_se_x_16][]

[https_leetcode-cn.com_problems_combination-sum]: https://leetcode-cn.com/problems/combination-sum/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5Yqq5Yqb5a2m5Lmg55qE5qKF5a2Q_size_19_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/01fb33b73054421e84623132f7cdff5f.png