组合总和 III（力扣第216题）

题目：

　　找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

　　所有数字都是正整数。
　　解集不能包含重复的组合。

示例：

输入: k = 3, n = 7
输出: [[1,2,4]]

分析：

　　明确题目的限制条件：1、组合中只允许存在1-9的数字；2、组合中元素的个数是k个；3、k个1-9范围内的数相加之和为n；4、组合中的元素不允许重复

　　可见，限制条件有很多，还是采用DFS和回溯的方法求解，只不过现在DFS的搜索路径长度有了固定的长度，也就是k，并且搜索过程中，每个节点的值只能是1-9的数。不能重复可以通过将下一次搜索的节点值设置为当前搜索节点值加1，这样就保证了不会产生重复得数字。在搜索的过程中，一旦搜索路径达到了规定长度并且此时路径上的节点值之和并不是n那么就立刻返回。

　　总之，整体的思路，和组合一、二差不多，只不过加一些条件即可。

具体的代码实现如下：

private List<List<Integer>> reslist;

    public List<List<Integer>> combinationSum3(int k, int n) {

        if (k > n){
            return new ArrayList<>();
        }

        reslist = new ArrayList<>();
        List<Integer> curlist = new ArrayList<>();

        combinationCur(k,1,n,curlist);

        return reslist;
    }

    private void combinationCur(int k, int s,int n, List<Integer> curlist) {

        if (curlist.size() == k && n != 0){
            return;
        }
        if (n == 0){

            if (curlist.size() == k){
                reslist.add(new ArrayList<>(curlist));

            }

            return;
        }

        for (int i = s; i <= 9; i++) {

            curlist.add(i);
            combinationCur(k,i+1,n-i,curlist);
            curlist.remove(curlist.size()-1);
        }

    }

组合总和 III（力扣第216题）

相关推荐