R8-回溯篇
印象题，很基本的回溯
class Solution {void backtrack(List<Integer> state,int target,int[] choices,int start,List<List<Integer>> ret){//子集和等于target，记录解if (target==0){ret.add(new ArrayList<>(state));return;}//遍历所有选择//剪枝2：从start开始遍历，避免生成重复子集for (int i=start;i<choices.length;i++){//剪枝1：若子集和超过target，直接结束循环if (target-choices[i]<0){break;}//做出选择,更新targetstate.add(choices[i]);//进行下一轮选择backtrack(state,target-choices[i],choices,i,ret);//回退:撤销选择，恢复到之前的状态state.remove(state.size()-1);}}public List<List<Integer>> combinationSum(int[] candidates, int target) {//状态子集List<Integer>state=new ArrayList<>();Arrays.sort(candidates);int start=0;//结果子集List<List<Integer>> ret=new ArrayList<>();backtrack(state,target,candidates,start,ret);return ret;}
} 
PS：
java语法
1.移除数组最后一个元素
state.remove(state.size()-1);2.使用数组接受传入的参数值
new ArrayList<>(state)3.ret数组后面增加值
ret.add()4.数组排序，例如candidates是一个数组
Arrays.sort(candidates);
