Question:

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.

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.
Example 1:

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

Example 2:

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

Thinking:

  • Method:
    1. 还是考虑回溯，每次尝试添加一个元素，继续往下传递。
    2. （自己没想到的地方）为了去重，我们传递一个start，每次从start开始遍历，这样就不会出现一个list通过组合的形式出现多次。
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(candidates == null || candidates.length == 0)
            return result;
        traceback(target, new ArrayList<Integer>(), result, candidates, 0);
        return result;
    }
    public static void traceback(int target, List<Integer> list, List<List<Integer>> result, int[] candidates, int start){
        if(target == 0)
            result.add(new ArrayList<>(list));
        else if(target < 0){
            return;
        }else{
            for(int i = start; i < candidates.length; i++){
                list.add(candidates[i]);
                traceback(target - candidates[i], list, result, candidates, i);
                list.remove(list.size() - 1);
            }
        }
    }
}

二刷

  1. 记得曾经用过Start来去重，但是二刷的时候仍然没有回忆起来。
  2. 通过提前排序，在for循环中根据temp跳出循环。
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates);
        backtrace(result, new ArrayList<Integer>(), 0, candidates, target, 0);
        return result;
    }
    private void backtrace(List<List<Integer>> result, List<Integer> temp, int sum, int[] candidates, int target, int start){
        if(sum == target){
            result.add(new ArrayList<Integer>(temp));
        }else if(sum < target){
            for(int i = start; i < candidates.length; i++){
                if(sum + candidates[i] > target) break;
                temp.add(candidates[i]);
                backtrace(result, temp, sum + candidates[i], candidates, target, i);
                temp.remove(temp.size() - 1);
            }
        }
    }
}

Third time

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new LinkedList<>();
        if(candidates == null || candidates.length == 0) return result;
        dfs(result, candidates, 0, target, new LinkedList<>(), 0);
        return result;
    }
    public void dfs(List<List<Integer>> result, int[] candidates, int index, int target, List<Integer> temp, int sum){
        if(target == sum){
            result.add(new LinkedList<Integer>(temp));
        }else if(sum < target){
            for(int i = index; i < candidates.length; i++){
                if(sum + candidates[i] > target) continue;
                temp.add(candidates[i]);
                dfs(result, candidates, i, target, temp, sum + candidates[i]);
                temp.remove(temp.size() - 1);
            }
        }
    }
}