LeetCode216. 组合总和 III

 简单的dfs问题,标记每一个数用没用过,没用过就用,v[i]=true,k--,n-=i,然后回溯就只需要将他们还原就行,注意这里是不能重复选,因此下一次选择的应该比这次要大,所以循环每次的初值是i=idx+1

class Solution {
    public List<List<Integer>> ans = new ArrayList<List<Integer>>();
    public boolean[] v = new boolean[11];
    public void dfs(int idx,int k,int n) {
        if(n < 0 || idx > 9 || k < 0)
            return;
        if(n == 0 && k == 0) {
            List<Integer> tmp = new ArrayList<Integer>();
            for(int i = 1;i < 10;i++) 
                if(v[i])
                    tmp.add(i);
            ans.add(tmp);
        }
        for(int i = idx + 1;i < 10;i++) {
            if(!v[i]) {
                v[i] = true;
                --k;
                n -= i;
                dfs(i,k,n);
                v[i] = false;
                ++k;
                n += i;
            }
        }
    }
    public List<List<Integer>> combinationSum3(int k, int n) {
        ans.clear();
        dfs(0,k,n);
        return ans;
    }
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏封碎

不小心犯的一个空指针错误 JavaEclipseIDEIDEAJVM

      今天碰到了一个空指针异常,代码看起来很普通,一点也看不出会空指针,后来debug才发现了问题所在。这是很容易忽略的地方,记一笔,不知道大家有没有碰到...

14720
来自专栏linux驱动个人学习

Linux内存描述之内存节点node--Linux内存管理(二)

这点前面是说的很明白了, NUMA结构下, 每个处理器CPU与一个本地内存直接相连, 而不同处理器之前则通过总线进行进一步的连接, 因此相对于任何一个CPU访问...

46220
来自专栏计算机视觉与深度学习基础

Leetcode 274. H-Index

Given an array of citations (each citation is a non-negative integer) of a rese...

22480
来自专栏Java架构师历程

spring boot应用启动原理分析

摘要: spring boot quick start 在spring boot里,很吸引人的一个特性是可以直接把应用打包成为一个jar/war,然后这个jar...

87930
来自专栏Samego开发资源

数据库Dao层抽象出BasicDao类 | 许久没碰Java了、致Java初学者

19240
来自专栏battcn

一起来学SpringBoot | 第十八篇:轻松搞定全局异常

实际项目开发中,程序往往会发生各式各样的异常情况,特别是身为服务端开发人员的我们,总是不停的编写接口提供给前端调用,分工协作的情况下,避免不了异常的发生,如果直...

16020
来自专栏Java进阶之路

高并发情景下避免使用SimpleDateFormat

19700
来自专栏Jed的技术阶梯

zookeeper案例之4个逻辑思维训练小题目

14120
来自专栏玩转JavaEE

SpringBoot中自定义参数绑定

本文是vhr系列的第十篇,vhr项目地址https://github.com/lenve/vhr 正常情况下,前端传递来的参数都能直接被SpringMVC接...

48850
来自专栏IT杂记

DateFormat 线程不安全

一、测试 测试代码如下:  private static SimpleDateFormat sdf = new SimpleDateFormat("yy...

21850

扫码关注云+社区

领取腾讯云代金券