专栏首页算法修养LeetCode 216. Combination Sum III(DFS)

LeetCode 216. Combination Sum III(DFS)

题目

题意:从1-9中选出k个数之和等于n,这个k个数不能有相同的,输出所有可能的k个数字的集合,结果也不能重复

题解:暴搜,从n开始,每次减去1-9中的某个数字,然后继续递归。要注意剪枝,比如1-9中的数字大于n/k的是不可能存在答案中的,如果n 的值小于sum[k]也是不会有答案的。sum[k]表示k个数字最小和的组合。当然k>=10的时候,也是没有答案的。

class Solution {
public:
    vector<vector<int>> res;
    vector<int> ans;
    map<int,int>m;
    int sum[10]={0,1,3,6,10,15,21,28,36,45};
    vector<vector<int>> combinationSum3(int k, int n) {
        
        if(k==0)
            return res;
        
        fun(n,k);
        
        return res;
        
    }
    
    void fun(int n,int k)
    {
        if(k==0)
        {
            if(n==0)
                res.push_back(ans);
            return;
        }

        
        if(n < sum[k] || k>=10)
            return;
        
        int i=1;
        if(ans.size()!=0)
            i = ans[ans.size()-1] + 1;
        for(;i<=9&&i<=n/k;i++)
        {
            if(m[i]!=0)
                continue;
            if(n<i)
                break;
            ans.push_back(i);m[i]=1;
            fun(n-i,k-1);
            ans.pop_back();m[i]=0;
        }
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDU 1525 Euclid's Game

    ShenduCC
  • pta习题集5-16 朋友圈

    某学校有N个学生,形成M个俱乐部。每个俱乐部里的学生有着一定相似的兴趣爱好,形成一个朋友圈。一个学生可以同时属于若干个不同的俱乐部。根据“我的朋友的朋友也是我...

    ShenduCC
  • HDU 1232 畅通工程(Kruskal)

    畅通工程 Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Jav...

    ShenduCC
  • Codeforces Round #507 Div.2 B. Shashlik Cooking(思维)

    题目链接:http://codeforces.com/contest/1040/problem/B

    Ch_Zaqdt
  • 牛客网平台常州大学新生寒假训练会试

    Zoctopus
  • 【CodeForces 699A】Launch of Collider

    饶文津
  • 【USACO 2.2】Party Lamps

    四种开关,n盏灯,1:改变所有灯状态,2:改变奇数灯状态,3:改变偶数灯状态,4:改变3k+1灯状态

    饶文津
  • pta习题集5-16 朋友圈

    某学校有N个学生,形成M个俱乐部。每个俱乐部里的学生有着一定相似的兴趣爱好,形成一个朋友圈。一个学生可以同时属于若干个不同的俱乐部。根据“我的朋友的朋友也是我...

    ShenduCC
  • 程序员面试金典 - 面试题 16.22. 兰顿蚂蚁(deque模拟)

    一只蚂蚁坐在由白色和黑色方格构成的无限网格上。 开始时,网格全白,蚂蚁面向右侧。 每行走一步,蚂蚁执行以下操作。

    Michael阿明
  • Android实现Camera2预览和拍照效果

    网上对于 Camera2 的介绍有很多,在 Github 上也有很多关于 Camera2 的封装库,但是对于那些库,封装性太强,有时候我们仅仅是需要个简简单单的...

    砸漏

扫码关注云+社区

领取腾讯云代金券