39.组合总数

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

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

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

：做题思考全过程

思路难点：想到传入这个idx参数，否则会出现res结果中出现重复的（顺序不同）list结果。

class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> temp = new ArrayList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {backtrace(candidates, target, 0);return res;}// 将传入数组和当前需要的sum？// idx记录上一个递归增加的元素的下标，让本次遍历增加元素从这个下标开始public void backtrace(int[] candidates, int target, int idx){// 不能写一起，不让第一个条件判断不符合直接会执行下面语句，根本不会看第二个判断条件// 顺序错了，要先判断是否target符合条件，再判断直接去重if(candidates[idx] > target) return;// if(target < 0 || candidates[idx] > target) return;if(target < 0) return;if(target == 0){// 去重？if(!res.contains(temp)) res.add(new ArrayList(temp));return;}// candidates数组是递增的？// 不是递增的。不适合用下面语句剪枝优化// if(candidates[idx] > target) return;// 也可以先对candidates数组排序，再使用这个优化// for遍历candidates// 为了达到去重目的，不让i从0开始遍历。改为for(int i = idx; i < candidates.length; i++){temp.add(candidates[i]);backtrace(candidates, target - candidates[i], i);temp.remove(temp.size()-1);}}}

：默写一遍，加深印象

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