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

相关文章

来自专栏LeetCode

LeetCode SingleNumber I,II,III

Given a non-empty array of integers, every element appears twice except for one....

1010
来自专栏开发技术

排序之快速排序(上)

希尔排序相当于直接插入排序的优化,它们同属于插入排序类,堆排序相当于简单选择排序的优化,它们同属于选择排序类。而快速排序其实就是冒泡排序的升级,它们都属于交换...

1833
来自专栏swag code

SmallSum-归并排序-小和问题(逆序对)

例如:数组[4,2,5,1,7,3,6] 第一个元素4比2大,不算小和,5比4和2都大,那就是4+2=6;1比4和2和5都小,不算小和;7比前面的都大,那就是上...

603
来自专栏XAI

程序员必知的8大排序(java实现)

8种排序之间的关系: ?  1、 直接插入排序   (1)基本思想:   在要排序的一组数中,假设前面(n-1)[n>=2] 个数已经是排好顺序的,现在要...

18010
来自专栏专注研发

poj-3185-开关问题

牛一行20他们喝的水碗。碗可以那么(面向正确的为清凉水)或颠倒的(一个位置而没有水)。他们希望所有20个水碗那么,因此用宽鼻子翻碗。

863
来自专栏Bingo的深度学习杂货店

Q35 Search Insert Position

Given a sorted array and a target value, return the index if the target is found...

2637
来自专栏攻城狮的动态

简谈归并排序

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

Leetcode 241. Different Ways to Add Parentheses

Given a string of numbers and operators, return all possible results from compu...

1769
来自专栏codingforever

经典算法巡礼(一) -- 排序之冒泡排序

事实上,她重复地遍历需要排序的元素,一次比较相邻的两个元素,如果不满足预先定义的比较条件,则交换;否则继续下一组元素比较,直至遍历完成需要排序的所有元素。当然,...

242
来自专栏李智的专栏

leetcode(1)Two Sum

Given an array of integers, return indices of the two numbers such that they add...

611

扫码关注云+社区