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

本文主要是介绍【回溯算法】四、回溯模板，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

这篇关于【回溯算法】四、回溯模板的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！