[LeetCode] 216. Combination Sum III

【原题】

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

【解释】 不同于Combination Sum和Combination Sum II,这里没有给定候选集合,而是使用数字1-9作为候选元素,并且要求指定结果集合的元素个数。统一元素在一个结果集合当中不能重复使用 【思路】 基本和Combination Sum II思想一样,只不过最后找到了和为target时,要判断其元素的个数是否与题目要求一样。

public class Solution {
   public void scombinationSum3Core(List<List<Integer>> results, List<Integer> result,int level,int k,int n,int sum){
        if(sum==n&&result.size()==k) {//判断元素个数和sum是否满足要求
            results.add(new ArrayList<Integer>(result));
            return;
        }
        if(result.size()==k) return;
        for(int i=level;i<10;i++){
            result.add(i);
            sum+=i;
            scombinationSum3Core(results,result,i+1,k,n,sum);
            sum-=i;
            //System.out.println(result);
            result.remove(result.size()-1);

        }
    }
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> results=new ArrayList<List<Integer>>();
        List<Integer> result=new ArrayList<>();
        scombinationSum3Core(results,result,1,k,n,0);
        return results;
    }

}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏编程

浅谈Go语言中闭包的使用

闭包(Closure),又称词法闭包(Lexical Closure)或函数闭包(function closures),是引用了自由变量的函数。这个被引用的自由...

2508
来自专栏Python小屋

Python编程一定要注意的那些“坑”(四)

已发过的“坑”请参考Python函数默认值参数的2个坑,Python编程中一定要注意的那些“坑”(一),Python编程中一定要注意的那些“坑”(二),Pyth...

33313
来自专栏Python小屋

Python 3.6.x字符串格式化方法小结

1 使用%符号进行格式 使用%符号进行字符串格式化的形式如下图所示,格式运算符%之前的部分为格式字符串,之后的部分为需要进行格式化的内容。 ? Python...

2586
来自专栏Android开发指南

9:集合collection

2766
来自专栏数据结构与算法

极值问题

背景 小铭的数学之旅2。 描述 已知m、n为整数,且满足下列两个条件: ① m、n∈1,2,…,K ② (n^ 2-mn-m^2)^2=1 编一程序,对给定K,...

3195
来自专栏技术专栏

无向图最短路径问题

题目:无向图G有N个结点(1<N<=1000)及一些边,每一条边上带有正的权重值。 找到结点1到结点N的最短路径,或者输出不存在这样的路径。

782
来自专栏nummy

itertools模块详解

tee()创建的迭代器共享其输入迭代器,所以一旦创建了新迭代器,就不应该再使用远迭代器。

843
来自专栏老马说编程

(53) 剖析Collections - 算法 / 计算机程序的思维逻辑

之前几节介绍了各种具体容器类和抽象容器类,上节我们提到,Java中有一个类Collections,提供了很多针对容器接口的通用功能,这些功能都是以静态方法的方式...

2089
来自专栏来自地球男人的部落格

[LeetCode] 40. Combination Sum II

【原题】 Given a collection of candidate numbers (C) and a target number (T), fi...

1795
来自专栏积累沉淀

Java设计模式(五)----原型模式

原型模式(Prototype) 一、概述 二、结构 三、浅度克隆和深度克隆  浅度克隆  深度克隆 一、概述  定义:原型模式属...

1839

扫码关注云+社区