算法训练营Day25(回溯)

2023-12-23 17:46:40

216.组合总和III

216. 组合总和 III - 力扣（LeetCode）

?

class Solution {
    private List<Integer> path = new ArrayList<>();
    private List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        backTracking(k,n,0,1);
        return result;
    }
    void backTracking(int k,int targetSum,int sum,int startIndex){
        if(path.size()==k){
            //剪枝
            if(sum>targetSum) return;
            if(targetSum==sum){
                result.add(new ArrayList<>(path));
            }
            return;
        }
        //5个数，找3个（k-path.size()），那么最多到5-3+1 也就是3这个下标
        for(int i = startIndex;i<=9-(k-path.size())+1;i++){
            //单层逻辑
            sum+=i;
            path.add(i);
            //递归
            backTracking(k,targetSum,sum,i+1);
            //回溯
            sum-=i;
            path.removeLast();
        }

    }
}

?17.电话号码的字母组合?

17. 电话号码的字母组合 - 力扣（LeetCode）

对java来说，String操作没有那么方便，就要接住StringBuilder，多了一个成员变量。

这里用temp操作，也就不涉及隐藏回溯逻辑这一说了。

class Solution {
    List<String> list = new ArrayList<>();
    //收获单个结果
    StringBuilder temp = new StringBuilder();
    public List<String> letterCombinations(String digits) {
        if(digits==null || digits.length()==0) return list;
         //初始对应所有的数字，为了直接对应2-9，新增了两个无效的字符串""
        String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        backTrackding(digits,numString,0);
        return list;
    }

    void backTrackding(String digits,String [] numString,int index){
        if(index == digits.length()){
            //结构收集
            list.add(temp.toString());
            return ;
        }
        //按下数字之后的字符串
        String str = numString[digits.charAt(index)-'0'];//-'0'str变为int
        //单层逻辑
        for(int i = 0;i<str.length();i++){
            temp.append(str.charAt(i));
            backTrackding(digits,numString,index+1);
            //回溯
            temp.deleteCharAt(temp.length()-1);
        }
    }
}

文章来源:https://blog.csdn.net/weixin_65728526/article/details/135166778
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。