class Solution {
//1.全局变量,这样方便回溯方法少点参数传递,看起来直观点
List<List<Integer>> res = new ArrayList<>();
Deque<Integer> path = new ArrayDeque<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
//2.1根据题意可要可不要,
//预处理待回溯数组,
//比如用到used数组时需要排序待回溯数组nums为升序;
int[] used = new int[candidates.length];//预处理部分,0未用1用,默认为0未用
Arrays.sort(candidates);//升序,方便让值一样的元素连续着,然后进行第22行的判断。
backTracking(target,candidates,0);
return res;
}
void backTracking(int n, int[] candidates, int start){
//3.给个递归终止条件;
if(n < 0)
return;
if(n == 0){
res.add(new ArrayList<>(path));
return;
}
//4.遍历同层所有元素
for(int i = start; i < candidates.length; i++){
//4.1根据题意可要可不要,
//如果前后俩元素值一样且第一个元素为首的情况已经加入了结果集,
//则跳过后面所有以重复元素防止结果集元素重复;
if(i > 0 && candidates[i-1] == candidates[i] && used[i-1] == 0)
continue;
//5.path添加这个被遍历的元素;
path.addLast(candidates[i]);
//5.1根据题意可要可不要;
used[i] = 1;
backTracking(n-candidates[i],candidates,i);
//6.**回退**path到没添加该元素的状态;
path.removeLast();
//6.1根据题意可要可不要;
used[i] = 0;
}
}
}
作者:ucasswk
链接:https://leetcode-cn.com/problems/binary-tree-paths/solution/yi-kan-jiu-dong-hui-su-suan-fa-tong-ji-e-iwbn/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。