leetcode - [216] Combination Sum III

2020/06/18

问题描述

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.

给你一个正整数k代表组合成正整数n的个数,使用1-9,且每个数字只能使用一次,请问有多少种组合方法?

Note:

All numbers will be positive integers.
The solution set must not contain duplicate combinations.

举个例子:

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]]

Update at 2020_0907

和其他几道组合求和题类似,直接看下实现:

class Solution {

    List<List<Integer>> ans = new LinkedList<>();

    private void dfs(int k, int t, LinkedList<Integer> child, int u, int sum){
        if (child.size() == k && sum == t){
            ans.add(new LinkedList<>(child));
            return;
        } else if (sum > t){
            return;
        }

        for (int i = u; i < 10; i++){
            child.add(i);
            dfs(k, t, child, i + 1, sum + i);
            child.removeLast();
        }
    }

    public List<List<Integer>> combinationSum3(int k, int n) {
        dfs(k, n, new LinkedList<>(), 1, 0);
        return ans;
    }
}

解法1

Thanks @topcoder811

我的思路是这样的:

首先,因为有k的限制,所以最深只能递归至k层,那么问题来了,如何做到仅递归到k层?

且若加上第k层的当前元素,还不够n,则如何继续遍历第k层的剩余元素?

关键来了,子列表child中的数量就可以代表层数!

所以,有了如下代码:

if (remain == 0 && child.size() == k){
    ans.add(new LinkedList<>(child));
    return;
}

接着,由于1-9每个数字只能使用一次,所以cur = i + 1

最后,注意一点,为了避免无效的遍历,可以在递归函数的首部添加如下限制条件:

if (child.size() > k){
    return;
}

来看下完整实现:

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        
        List<List<Integer>> ans = new LinkedList<>();
        bt(k, n, ans, new LinkedList<>(), 1);
        return ans;
    }
    
    private void bt(int k, int remain, List<List<Integer>> ans, 
                    LinkedList<Integer> child, int start){
        
        if (child.size() > k){
            return;
        }
        
        if (remain == 0 && child.size() == k){
            ans.add(new LinkedList<>(child));
            return;
        }
        
        for (int i = start; i <= 9; i++){
            child.add(i);
            bt(k, remain - i, ans, child, i + 1);
            child.removeLast();
        }
    }
}

Enjoy it !


一位喜欢提问、尝试的程序员

(转载本站文章请注明作者和出处 姚屹晨-yaoyichen

Post Directory