首页 > 其他分享 >刷刷刷 Day 25 | 216. 组合总和 III

刷刷刷 Day 25 | 216. 组合总和 III

时间:2023-01-28 11:23:16浏览次数:67  
标签:216 25 组合 int res sum path III

216. 组合总和 III

LeetCode题目要求

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

只使用数字1到9
每个数字 最多使用一次 
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。

示例

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。
解题思路

本题类似组合的解法, 刷刷刷 Day 24 | 77. 组合 ,根据回溯模板往下写即可,需要注意的就是有个加和的操作。与组合解法类似同样要进行剪枝优化

上代码

class Solution {
    private List<List<Integer>> res = null;
    private Deque<Integer> path = null;
    public List<List<Integer>> combinationSum3(int k, int n) {
        // k 是需要的数字的数量
        // n 是 k 个数字的和

        res = new ArrayList<>();
        path = new LinkedList<>();
        backtracking(k, n, 1, 0);
        return res;
    }

    private void backtracking(int k, int n, int startIndex, int sum) {
        // 剪枝操作,如果累加的 sum 已经大于目标值 n 了。就没必要继续下去
        if (sum > n) {
            return;
        }

        // 终止条件
        if (path.size() == k) {
            // 存储结果, 如果 sum 累加后与目标 n 相等,那么就存结果
            if (n == sum) {
                res.add(new ArrayList(path));
            }
            return;
        }

        // 遍历 i<n 可剪枝 
        for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {
            path.add(i);
            // 累加操作,计算范围内数字和
            sum += i;
            // 递归操作,
            backtracking(k, n, i + 1, sum);
            // 回溯操作
            sum -= i;
            path.removeLast();
        }
        
    }
}

附:学习资料链接

标签:216,25,组合,int,res,sum,path,III
From: https://www.cnblogs.com/blacksonny/p/17069912.html

相关文章

  • Qt-Qt之雷达扫描效果-No25-QtRadar
    相关资料:实例代码:.pro1QT+=coregui23greaterThan(QT_MAJOR_VERSION,4):QT+=widgets45CONFIG+=c++1167#Thefollowingdefinemakesyourcomp......
  • 第25章 web层开发-用户接口开发
    目录1表单验证的初始化2自定义mobile验证器3登录逻辑完善4session机制在微服务下的问题5jsonwebtoken的认证机制6集成jwt到gin中7给url添加登录权限验证8如何解......
  • 【双指针】LeetCode 125. 验证回文串
    题目链接125.验证回文串思路简单双指针应用代码classSolution{publicbooleanisPalindrome(Strings){StringBuffersgood=newStringBuffer();......
  • 罗-ZC4125-U盘刷系统方法
    关于罗ZC4125安装步骤 一、部署条件1.罗ZC4125PC2.16~32GU盘3.对应系统 二、部署步骤1.确认其PC型号  2.将U盘格式化为NTFS格式,并将卷标改为:“WINPE”......
  • [PR21657]和平共处
    为了方便,以下"上下左右"均基于通常的平面直角坐标系考虑未被喂食的蚂蚁,即构成最大独立集,也即可以看作:作一条从左上出发,不断向右/下的折线,最大化折线下方白点数+上方黑点......
  • POJ--3255 Roadblocks(最短路)
    记录0:252023-1-27http://poj.org/problem?id=3255reference:《挑战程序设计竞赛(第2版)》2.4.4p108DescriptionBessiehasmovedtoasmallfarmandsometimese......
  • 1.25刷题记录
    目录1.[GUET-CTF2019]虚假的压缩包2.[SWPU2019]Network3.[MRCTF2020]Hello_misc4.[MRCTF2020]Unravel!!5.[ACTF新生赛2020]music6.[CFI-CTF2018]webLogoncapture7.[MRCT......
  • [20230125]21c Force matching signature的计算.txt
    [20230125]21cForcematchingsignature的计算.txt--//昨天看了链接:https://hourim.wordpress.com/2023/01/22/force-matching-signature/--//里面提到计算force_matchin......
  • 【算法训练营day25】LeetCode216. 组合总和III LeetCode17. 电话号码的字母组合
    LeetCode216.组合总和III题目链接:216.组合总和III独上高楼,望尽天涯继续复健,一直在犯小的语法错误。慕然回首,灯火阑珊和昨天的题很像,主要区别在于递归返回条件和回溯......
  • POJ--3253 Fence Repair(贪心/优先队列)
    记录23:572023-1-25http://poj.org/problem?id=3253reference:《挑战程序设计竞赛(第2版)》2.2.4p47DescriptionFarmerJohnwantstorepairasmalllengthofth......