友链
姚屹晨

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