3月8日代码随想录组合总和Ⅲ

216.组合综合Ⅲ

216. 组合总和 III - 力扣（LeetCode）

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

• 只使用数字1到9
• 每个数字 最多使用一次 

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

示例 3:

输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。

提示:

• 2 <= k <= 9
• 1 <= n <= 60

思路

方法一组合枚举

这道题可以看成77.组合的变体，查找元素固定在了1~9，在找到长度为k的path时需要判断和是否为n，所以不考虑优化的情况下，代码和组合没有什么区别，只需要添加一个sum在将数加入path时记录当前path中数之和。

class Solution {
        public List<List<Integer>> combinationSum3(int k, int n) {
            List<List<Integer>> res=new ArrayList<>();
            Deque<Integer> path=new ArrayDeque<>();
            dfs(n,k,1,res,path,0);
            return res;
        }
        private void dfs(int n,int k,int begin,List<List<Integer>> res,Deque<Integer> path,int sum){
            if(path.size()==k&&sum==n){
                    res.add(new ArrayList<>(path));
                    return;
                }
            for(int i=begin;i<10;i++){
                path.addLast(i);
                sum+=i;
                
                dfs(n,k,i+1,res,path,sum);
                sum-=i;
                path.removeLast();
            }
        }
    }

另一种方法也是同一类，但是是考虑1~9中每个数选与不选，而且不使用栈来递归，减少了空间开销（吗）

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);
    }
}

方法二：二进制子集枚举

另一种想法是，组合中只有1~9的正整数，那么我们用9位二进制数来表示1~9中数的组合，第一位代表1，若第一位不为0则表示选择1.

这样，我们可以遍历0到2的9次方-1之间的所有二进制数来寻找所有答案，这样不会漏找也不会重复，第i位是否被选择使用(1<<i)&该二进制数来表示，又因为第0位代表1，所以在判断i位被选择时，将i+1加入sum。

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) {
            for(int mask=0;mask<(1<<9);mask++){
                if(check(mask,k,n)){
                    ans.add(new ArrayList<Integer>(temp));
                }
            }
            return ans;
        }
        public boolean check(int mask,int k,int n){
            temp.clear();
            for(int i=0;i<9;i++){
                if(((1<<i)&mask)!=0){
                    temp.add(i+1);
                }
            }
            if (temp.size() != k) {
                return false;
            }
            int sum=0;
            for(int num:temp){
                sum+=num;
            }
            return sum==n;
        }

    }

总结

目前回溯法接触到了三种解法，1、枚举下一个数选哪个2、枚举下一个数选不选3、枚举子集（和1相似但可以使用二进制的技巧）。

原文地址：https://blog.csdn.net/qq_39911747/article/details/136558585

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！