回溯-组合问题

针对回溯法，要把问题具象化为树结构。（第2题的树结构）

class Solution {
    List> res = new ArrayList<>();
    List temp = new ArrayList<>();
    public List> combine(int n, int k) {
        backtracking(n,k,1);
        return res;
    }
    public void backtracking(int n,int k,int start){
        if(temp.size()==k){
            res.add(new ArrayList(temp));
            return ;
        }
        剪枝:修改i<=n为i<=n-(k-temp.size())+1
        for(int i = start;i<=n;i++){
            temp.add(i);
            backtracking(n,k,i+1);
            temp.remove(temp.size()-1);
        }
    }
}

class Solution {
    List> res = new ArrayList<>();
    List temp = new ArrayList<>();
    int sum = 0;
    public List> combinationSum3(int k, int n) {
        backtraceking(k,n,1);
        return res;
    }
    public void backtraceking(int k,int n,int start){
        if(temp.size()==k&&sum==n){
            res.add(new ArrayList(temp));
            return;
        }
        for(int i = start;i<=9;i++){
            temp.add(i);
            sum+=i;
            backtraceking(k,n,i+1);
            temp.remove(temp.size()-1);
            sum-=i;
        }
    }
}
#########################################################
//剪枝版本
class Solution {
    List> res = new ArrayList<>();
    List temp = new ArrayList<>();
    int sum = 0;
    public List> combinationSum3(int k, int n) {
        backtraceking(k,n,1);
        return res;
    }
    public void backtraceking(int k,int n,int start){
    //考虑当前集合中的和大于了n就不可能满足条件，所以直接结束
        if(sum>n){
            return;
        }
        if(temp.size()==k&&sum==n){
            res.add(new ArrayList(temp));
            return;
        }
        //和题1一样，当剩余的元素个数不足需要的元素个数时停止
        for(int i = start;i<=9-(k-temp.size())+1;i++){
            temp.add(i);
            sum+=i;
            backtraceking(k,n,i+1);
            temp.remove(temp.size()-1);
            sum-=i;
        }
    }
}

class Solution {
    List res = new ArrayList<>();
    StringBuilder sb = new StringBuilder(); 
    public List letterCombinations(String digits) {
        String[] numString={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        if(digits.length()==0||digits==null){
            return res;
        }
        backtraceking(digits,numString,0);
        return res;
    }
    public void backtraceking(String digits,String[] numString,int start){
        if(sb.length()==digits.length()){
            res.add(sb.toString());
            return;
        }
        String str = numString[digits.charAt(start)-'0'];
        for(int i =0;i 
4.组合总和 leetcode 39 
class Solution {
    List> res = new ArrayList<>();
    List temp = new ArrayList<>();
    int sum = 0;
    public List> combinationSum(int[] candidates, int target) {
        backtraceking(candidates,target,0);
        return res;
    }
    public void backtraceking(int[] candidates, int target,int start){
        if(sum==target){
            res.add(new ArrayList(temp));
            return;
        }
        for(int i = start;itarget){
                break;
            }//剪枝操作，必须要在sum更新之前，要是更新之后sum之后会出行跳出但是sum没减少，temp违规元素没出栈
            temp.add(candidates[i]);
            sum+=candidates[i];
            backtraceking(candidates,target,i);
            sum-=candidates[i];
            temp.remove(temp.size()-1);
        }
    }
}
 
5.组合总和Ⅱ leetcode 40 
class Solution {
    List> res = new ArrayList<>();
    List temp = new ArrayList<>();
    int sum = 0;
    public List> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        backtraceking(candidates,target,0);
        return res;
    }
    public void backtraceking(int[] candidates,int target,int start){
        if(sum==target){
            res.add(new ArrayList(temp));
            return ; 
        }
        for(int i=start;istart&&candidates[i]==candidates[i-1]){
                continue;
            }
            temp.add(candidates[i]);
            sum+=candidates[i];
            backtraceking(candidates,target,i+1);
            temp.remove(temp.size()-1);
            sum-=candidates[i];
        }
    }
}
 
主要是要进行剪枝，为了剪枝方便，先将数组排序。我们剪枝的要求是：同一组合的数字可以重复，但是不同组合间不能重复。而回溯中，for循环代表了不同结果组合，递归代表了统一集合的后序字符。代入树中就是树层不能重复，树枝可以重复（而在循环时，当i=start时，肯定是树层的，树枝就是不等于start的）。