Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

candidates中的元素并不一定没有duplicates，但是可以重复使用同一个元素，所以并不需要Arrays.sort(), 而且dfs起始start还是同一个index i.

1
2
3
4
5
6
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]
1
2
3
4
5
6
7
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

因为主函数中dfs是target开始，所以是减少

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<List<Integer>> combinationSum(int[] nums, int target) {
        List<List<Integer>> list = new ArrayList<>();
        dfs(list, new ArrayList<>(), nums, target, 0);
        return list;
    }
    
    public void dfs(List<List<Integer>> list, List<Integer> arr, int[] nums, int target, int start) {
        if (target < 0) return ;
        else if (target == 0) list.add(new ArrayList<>(arr));
        for (int i = start; i < nums.length; ++i) {
            arr.add(nums[i]);
            dfs(list, arr, nums, target - nums[i], i); // not i+1 because elements can be reused
            arr.remove(arr.size() - 1);
        }
        
    }
}