【回溯算法】四、回溯模板

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)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
上一篇:391,回溯算法求组合问题


下一篇:面试腾讯算法:组合总和