LeetCode ● 216.组合总和III ● 17.电话号码的字母组合

LeetCode 216.组合总和III

分析1.0

回溯问题组合总和sum == n 时以及path中元素个数 == k 时，res.add(new path)

返回后递归删除掉当前值

class Solution {

    public List<List<Integer>> res = new ArrayList();

    public LinkedList<Integer> path = new LinkedList();

    public List<List<Integer>> combinationSum3(int k, int n) {

        backTracking(k, n, 1, 0, 0);

        return res;

    }

    public void backTracking(int k, int n, int start, int sum, int cnt){

        if(sum == n && cnt == k){

            res.add(new LinkedList(path));

            return;

        }

        for(int i = start; i <= 9; i++){

            path.add(i);

            sum+=i;

            cnt++;

            backTracking(k, n, i+1, sum, cnt);

            sum-=i;

            cnt--;

            path.removeLast();

        }

    }

}

分析2.0

剪枝已选元素总和如果已经大于n了，那么往后遍历就没有意义了，直接剪掉。
path 元素个数可以由path.size()获取，并不用弄一个元素个数计数器

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

分析1.0

这个题目有几个关键点：

字母间的组合依赖于输入数字，必然要建立数字同字母间的映射关系
数字个数决定了递归深度数字个数计数器，而字母个数决定了回溯单层逻辑每层宽度字母个数计数器
终止条件：当前字母组合长度 == 数字个数
回溯函数 void bk(输入数字组合，映射表，数字个数计数器）

class Solution {

    //设置全局列表存储最后的结果

    List<String> list = new ArrayList<>();

    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"};

        //迭代处理

        backTracking(digits, numString, 0);

        return list;

    }

    //每次迭代获取一个字符串，所以会设计大量的字符串拼接，所以这里选择更为高效的 StringBuild

    StringBuilder temp = new StringBuilder();

    //比如digits如果为"23",num 为0，则str表示2对应的 abc

    public void backTracking(String digits, String[] numString, int num) {

        //遍历全部一次记录一次得到的字符串

        if (num == digits.length()) {

            list.add(temp.toString());

            return;

        }

        //str 表示当前num对应的字符串

        String str = numString[digits.charAt(num) - '0'];

        for (int i = 0; i < str.length(); i++) {

            temp.append(str.charAt(i));

            //c

            backTracking(digits, numString, num + 1);

            //剔除末尾的继续尝试

            temp.deleteCharAt(temp.length() - 1);

        }

    }

}

总结

写完代码看剪枝
确定深度递归逻辑横向递归逻辑终止逻辑递归参数剪枝逻辑

巴特西

LeetCode ● 216.组合总和III ● 17.电话号码的字母组合

LeetCode 216.组合总和III

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

总结

最新文章

热门文章