组合总和3(中等题)

2020-09-12

216. 组合总和 III

难度中等275

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

说明：

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

示例 1:

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

示例 2:

1 2	输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]

class Solution {
    private List<List<Integer>> ans=new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {

        int maxCyc=n>9?9:n;
        int[] candidates=new int[maxCyc+1];
        boolean[] flags=new boolean[maxCyc+1];
        List<Integer> tempList=new ArrayList<>();//临时列表
        List<Integer> indexList=new ArrayList<>();//每个数字只能使用一次

        for(int i=0;i<maxCyc;i++){
            candidates[i]=i+1;
        }
        calc(candidates,k,n,flags,tempList,indexList,0,0);

        return ans;
    }

     public Integer calc(int[] candidates,int k, int target,boolean[] flags, List<Integer> tempList,
                               List<Integer> indexList,int start,int layer){

        if(layer>k){//超出层数，终止
            return target+1;
        }

        int sum=0;
        for(Integer val:tempList){
            sum+=val;
        }

        if(sum<target&& layer==k){//已经满足层数了，但是和还是小于，直接终止，换掉最后一个数字
            return target+1;
        }

        if(sum>=target){//无需继续算
            return sum;
        }
        for(int i=start;i<candidates.length;i++) {
            if (!flags[i]) {
                tempList.add(candidates[i]);
                flags[i] = true;
                indexList.add(i);
            } else {
                continue;
            }

            Integer val = calc(candidates, k,target, flags, tempList, indexList, i,layer+1);
            if (val == target) {
                List<Integer> tempAns = new ArrayList<>(tempList);//容器复制
                if(layer+1==k&&!ans.contains(tempAns)){//因为和是layer+1层的，判断layer+1是否满足k层，并且没有重复
                    ans.add(tempAns);
                }
            }

            tempList.remove(tempList.size() - 1);//移除上个轮次用的数字
            flags[indexList.get(indexList.size() - 1)] = false;//移除上个占用的数字
            indexList.remove(indexList.size() - 1);//坐标也移除，与上面对应
        }
        return target+1;
    }

}

评论区高效率解法


class Solution {
    List<List<Integer>> lists = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<Integer> list = new ArrayList<>();
        dfs(k,1,n,list);
        return lists;
    }
    
    public void dfs(int k,int index,int target,List<Integer> list){
        if(target == 0 && k == 0){
            lists.add(new ArrayList<Integer>(list));
            return;
        }
        if(target < index || k <= 0){
            return;
        }
        for(int i = index;i <= 9;i++){
            list.add(i);
            dfs(k-1,i+1,target-i,list);
            list.remove(list.size()-1);
        }
    }
}

组合枚举

class Solution {
    List<Integer> temp = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

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

    public void dfs(int cur, int n, int k, int sum) {
        if (temp.size() + (n - cur + 1) < k || temp.size() > k) {
            return;
        }
        if (temp.size() == k) {
            int tempSum = 0;
            for (int num : temp) {
                tempSum += num;
            }
            if (tempSum == sum) {
                ans.add(new ArrayList<Integer>(temp));
                return;
            }
        }
        temp.add(cur);
        dfs(cur + 1, n, k, sum);
        temp.remove(temp.size() - 1);
        dfs(cur + 1, n, k, sum);
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/combination-sum-iii/solution/zu-he-zong-he-iii-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。