leetcode 216. 组合总和 III

导读:本篇文章讲解 leetcode 216. 组合总和 III,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com



题目

找出所有相加之和为 n 的 k 个数的组合,且满足下列条件:

只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。
在这里插入图片描述
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/combination-sum-iii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思考

  • 1、和leetcode 77 组合题基本一致,就是我们循环递归的个数现在不是n来控制,而是就是9个嵌套
  • 2、题目要求我们需要总和,那么我们在递归函数中就需要定义一个sum,因为我们每次的值是不一样
  • 3、我们在回溯中不仅要将上一个元素弹出,去匹配另外一个树枝,并且需要重新计算sum值

代码和注释

class Solution {
    // 收集路径
    LinkedList<Integer> path = new LinkedList<>();
    // 结果集
    List<List<Integer>> result = new ArrayList<>();

    /**
        使用回溯法
        1、函数的参数
        2、终止条件按
        3、每轮递归干的事
     */
    public List<List<Integer>> combinationSum3(int k, int n) {
        backtacking(k, n, 0, 1);
        return result;
    }

    // 回溯函数 sum 是已经收集的总和
    public void backtacking(int k, int n,int sum, int startIdx){
        // 1、结束条件
        if(path.size() == k){
            // 当前和与目标和一致的时候需要收集结果
            if(sum == n){
                result.add(new ArrayList<>(path));
            }
            return;
        }
        // 2、每轮递归回溯要干的事(剪枝)
        for(int i = startIdx; i <= 9-(k - path.size()) + 1; i++){
            sum +=i;
            path.add(i);
            // 开始的下标向后走
            backtacking(k, n, sum, i + 1);
            // 回溯
            path.removeLast();
            sum -= i;
        }
    }
}

总结

  • 1、回溯递归三部曲
    • a:定义递归函数的参数
    • b:终止条件【大多数为path集合深度和目标长度一致返回,加一个目标结果收集】
    • c:每轮递归要干嘛【业务+最后回溯】
  • 2、优化剪枝:总长-(目标长度-收集的长度)【其实这里我们考虑的就是至多递归到的位置,然后我们收集的长度有没有到目标长度】

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由极客之家整理,本文链接:https://www.bmabk.com/index.php/post/96133.html

(0)
小半的头像小半

相关推荐

极客之家——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!