代码随想录算法训练营Day19

第77题. 组合

力扣题目链接：. - 力扣（LeetCode）

剪枝操作详解：

k-path.size():还需要的元素个数

n-(k-path.size())+1:能提供所需要元素个数的最大下标

class Solution {
    List<List<Integer>> result=new ArrayList<>();
    List<Integer> path=new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        backtracking(n,k,1);
        return result;
    }
    public void backtracking(int n,int k,int startindex){
        if(path.size()==k){
            result.add(new ArrayList<>(path));
            return;
        }
        for(int i=startindex;i<=n-(k-path.size())+1;i++){
            path.add(i);
            backtracking(n,k,i+1);
            path.removeLast();
        }
    }
}

216.组合总和III

力扣题目链接：. - 力扣（LeetCode）

class Solution {
    List<List<Integer>> result=new ArrayList<>();
    List<Integer> path=new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
            backtracking(k,n,1);
            return result;
    }
    public void backtracking(int k,int n,int startindex){
        if(path.size()==k){
            int sum=0;
            for(int i=0;i<k;i++){
                sum+=path.get(i);
            }
            if(sum==n){
                result.add(new ArrayList<>(path));
            }
            return;
        }
        for(int i=startindex;i<=10-(k-path.size());i++){
            path.add(i);
            backtracking(k,n,i+1);
            path.removeLast();
        }
    }
}

17.电话号码的字母组合

力扣题目链接：. - 力扣（LeetCode）

class Solution {
    List<String> result=new ArrayList<>();
    StringBuilder temp=new StringBuilder();
    public List<String> letterCombinations(String digits) {
        if(digits==null||digits.length()==0){
            return result;
        }
        String[] table={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        backtracking(digits,table);
        return result;
    }
    public void backtracking(String digits,String[] table){
        if(temp.length()==digits.length()){
            result.add(temp.toString());
            return;
        }
       String str=table[digits.charAt(temp.length())-'0'];
        for(int i=0;i<str.length();i++){
            temp.append(str.charAt(i));
            backtracking(digits,table);
            temp.deleteCharAt(temp.length()-1);
        }
    }
}