39. 组合总和(简单)

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

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。
解集不能包含重复的组合。

示例 1：

输入：candidates = [2,3,6,7], target = 7
所求解集为：

1
2
3
4
[
  [7],
  [2,2,3]
]

示例 2：

输入：candidates = [2,3,5], target = 8
所求解集为：

1
2
3
4
5
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum

思路：

深度优先搜索

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> path= new ArrayList<Integer>();
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        dfs(candidates,target,path,res,0);
        return res;
    }
    //深度优先搜索
    void dfs(int[] candidates,int target,List<Integer> path,List<List<Integer>> res,int index){
        if(index==candidates.length){
            return;
        }
        //如果target为0，则终结
        if(target==0){
            res.add(new ArrayList<Integer>(path));
            return ;
        }
        //递归
        dfs(candidates,target,path,res,index+1);
        if(target-candidates[index]>=0){
            path.add(candidates[index]);
            dfs(candidates,target-candidates[index],path,res,index);
            path.remove(path.size()-1);
        }
    }
}