【leetcode hot 100 39】组合总和

错误解法一：每一次回溯都遍历提供的数组

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

错误原因：

• 没有回溯中止条件
• 未考虑到数字相同但是位置不同的情况，我们把这种情况也算作一次结果

解法一：（回溯法）每一次回溯尝试把第idx个数加进去，考虑重复使用candidates[idx]，或不使用candidates[idx]（即：跳过）

class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> result = new ArrayList<List<Integer>>();List<Integer> temp = new ArrayList<Integer>();int idx = 0; // 从第0个数开始回溯backtrack(candidates, target, result, temp, idx);return result;}public void backtrack(int[] candidates, int target, List result, List temp, int idx){// temp拿到所有candidateif (idx == candidates.length) {return;}if(target==0){result.add(new ArrayList<Integer>(temp)); // 这里要new，不能直接add tempreturn;}// 选择当前数if(target-candidates[idx]>=0){temp.add(candidates[idx]);backtrack(candidates, target-candidates[idx], result, temp, idx);temp.remove(temp.size()-1);}// 不选择当前数，直接回溯backtrack(candidates, target, result, temp, idx+1);}
}

注意：

• 这里要new，不能直接result.add(temp)：result.add(new ArrayList<Integer>(temp))
• 结束标值：
  • temp拿到所有candidate
  • 找到和为target的序列
• 当target-candidates[idx]>=0时，要选择当前数