仅为个人记录复盘学习历程，解题思路来自代码随想录
代码随想录刷题笔记总结网址:
代码随想录
39. 组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。
提供参数：int数组candidates，目标数值target。
主要操作：
递归三要素
1.返回值类型和输入参数：
遍历整棵解空间树，使用全局变量res作为结果集，使用全局变量path记录单条结果，返回值类型为void，需要输入candidates数组作为参数，还有目标值target，起始位置startIndex（避免额外操作），累加和sum。
2.终止条件：
2.1sum与目标值target相同，将结果记录到结果集中，返回。
2.2sum大于目标值target，直接返回。
3.单层递归逻辑：
从起始索引位置startIndex遍历数组candidates，在遍历时递归向下探索解空间树，同时返回时进行回溯。
代码大致如下：
public List<List<Integer>>res=new ArrayList<>();public List<Integer>path=new ArrayList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {//由于for循环条件判断时使用了剪枝，这里需要排序，否则会缺失部分结果。Arrays.sort(candidates);backTrace(candidates,target,0,0);return res;} public void backTrace(int[]candidates,int target,int sum,int startIndex){//终止条件if(sum==target){res.add(new ArrayList(path));return;}//单层递归逻辑//sum+candidates[i]<=target此处进行剪枝。for(int i=startIndex;i<candidates.length&&sum+candidates[i]<=target;i++){sum+=candidates[i];path.add(candidates[i]);backTrace(candidates,target,sum,i);path.remove(path.size()-1);sum-=candidates[i];}}自己尝试解题的代码（虽然能通过但是很乱）：
public List<List<Integer>>res=new ArrayList<>();public List<Integer>path=new ArrayList<>();public int value;public List<List<Integer>> combinationSum(int[] candidates, int target) {backTrace(candidates,target);return res;} public void backTrace(int[]candidates,int target){//终止条件if(value==target){List<Integer>temp2=new ArrayList(path);Collections.sort(temp2);for(int i=0;i<res.size();i++){List<Integer>temp1=new ArrayList(res.get(i));Collections.sort(temp1);if(temp1.equals(temp2)){return;}}res.add(new ArrayList(path));return;}//单层递归逻辑for(int i=0;i<candidates.length&&(value<=target);i++){path.add(candidates[i]);value+=candidates[i];backTrace(candidates,target);value-=candidates[i];path.remove(path.size()-1);}}这个问题感觉和背包问题有些相似之处，但不完全等同。