R8-回溯篇

印象题，很基本的回溯

java">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.移除数组最后一个元素

java">state.remove(state.size()-1);

2.使用数组接受传入的参数值

java">new ArrayList<>(state)

3.ret数组后面增加值

java">ret.add()

4.数组排序，例如candidates是一个数组

java">Arrays.sort(candidates);