[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 条评论
登录 后参与评论

相关文章

来自专栏菩提树下的杨过

javascript:双链表-插入排序

数组存储前提下,插入排序算法,在最坏情况下,前面的元素需要不断向后移,以便在插入点留出空位,让目标元素插入。 换成链表时,显然无需做这种大量移动,根据每个节点的...

21210
来自专栏眯眯眼猫头鹰的小树杈

leetcode347. Top K Frequent Elements

这里有一个额外要求即时间复杂度要优于O(n log n),也就是说我们无法采用先排序再顺序计算的方式来进行统计,因为最好的排序算法其平均的时间复杂度也需要O(n...

592
来自专栏Java Web

数据结构与算法(4)——优先队列和堆什么是优先队列?堆和二叉堆LeetCode相关题目整理

听这个名字就能知道,优先队列也是一种队列,只不过不同的是,优先队列的出队顺序是按照优先级来的;在有些情况下,可能需要找到元素集合中的最小或者最大元素,可以利用优...

2441
来自专栏java工会

java集合详解

21310
来自专栏F_Alex

数据结构与算法(四)-线性表之循环链表

前言:前面几篇介绍了线性表的顺序和链式存储结构,其中链式存储结构为单向链表(即一个方向的有限长度、不循环的链表),对于单链表,由于每个节点只存储了向后的指针,到...

1583
来自专栏大闲人柴毛毛

图的遍历(BFS+DFS)

图的遍历与树的遍历基本类似,但要注意两个不同: 1. 图中可能有环路,因此可能会导致死循环; 2. 一个图可能由多个独立的子图构成,因此一条路径走到头...

41911
来自专栏java一日一条

Java 容器 & 泛型(2):ArrayList 、LinkedList和Vector比较

序列(List),有序的Collection,正如它的名字一样,是一个有序的元素列表。确切的讲,列表通常允许满足 e1.equals(e2) 的元素对 e1 和...

681
来自专栏自学笔记

Data Structure堆Tree并查集图论

堆这种数据结构的应用很广泛,比较常用的就是优先队列。普通的队列就是先进先出,后进后出。优先队列就不太一样,出队顺序和入队顺序没有关系,只和这个队列的优先级相关,...

734
来自专栏微信公众号:Java团长

Java HashMap的工作原理

面试的时候经常会遇见诸如:“java中的HashMap是怎么工作的”,“HashMap的get和put内部的工作原理”这样的问题。本文将用一个简单的例子来解释下...

532
来自专栏老马说编程

(55) 容器类总结 / 计算机程序的思维逻辑

从38节到54节,我们介绍了多种容器类,本节进行简要总结,我们主要从三个角度进行总结: 用法和特点 数据结构和算法 设计思维和模式 用法和特点 我们在52节...

2067

扫码关注云+社区