关注Java领域相关技术 记录有趣的事情

LeetCode-216. 组合总和 III

US-B.Ralph
US-B.Ralph
2020-09-11

问题地址

LeetCode每日一题/2020-09-11

LeetCode216. 组合总和 III


问题描述

规则

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

说明

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

示例

  • 示例一:
输入: k = 3, n = 7
输出: [[1,2,4]]
  • 示例二:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

解析

解题思路

数据操作分析

  • 使用递归;
  • 递归终止条件:
    • 当前答案集中元素数量>k
    • 当前n<0
    • 当前答案集中元素个数==k 且 n==0

复杂度分析

  1. 时间复杂度
  2. 空间复杂度

编码实现

/**
 * LeetCode0216
 */
public class LeetCode0216_CombinationSumiii {

    /**
     * @param k k个数的组合
     * @param n 和为n
     * @return
     */
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> ans = new ArrayList<>();
        Map<List<Integer>, Integer> map = new HashMap<>();
        List<Integer> tmp = new ArrayList<>();
        int start = 1;
        dfs(k, n, ans, tmp, start);
        return ans;
    }

    private void dfs(int k, int n, List<List<Integer>> ans, List<Integer> tmp, int start) {
        if (n < 0 || n > 45 || k < 1 || k > 9) return;

        //找到符合要求的组合
        if (tmp.size() == k && n == 0) {
            ans.add(new ArrayList<>(tmp));
            return;
        }

        for (int i = start; i <= 9; i++) {
            tmp.add(i);
            dfs(k, n - i, ans, tmp, i + 1);
            tmp.remove(tmp.size() - 1);//最后添加的先删除
        }
    }
}


官方解法

方法一:二进制(子集)枚举

思路:

  • 「组合中只允许含有 1−9 的正整数,并且每种组合中不存在重复的数字」意味着这个组合中最多包含 9 个数字。我们可以把原问题转化成集合 S ={1,2,3,4,5,6,7,8,9 },我们要找出 SS 的当中满足如下条件的子集:
    • 大小为 k
    • 集合中元素的和为 n
  • 因此我们可以用子集枚举的方法来做这道题。即原序列中有 9 个数,每个数都有两种状态,「被选择到子集中」和「不被选择到子集中」,所以状态的总数为 2^9。我们用一个 9 位二进制数 \rm mask 来记录当前所有位置的状态,从第到高第 i 位为 0 表示 i 不被选择到子集中,为 1 表示 i 被选择到子集中。当我们按顺序枚举 [0, 2^9 – 1] 中的所有整数的时候,就可以不重不漏地把每个状态枚举到,对于一个状态 \rm mask,我们可以用位运算的方法得到对应的子集序列,然后再判断是否满足上面的两个条件,如果满足,就记录答案。
  • 如何通过位运算来得到 \rm mask 各个位置的信息?对于第 i 个位置我们可以判断 (1 << i ) & mask 是否为 0,如果不为 0 则说明 i 在子集当中。当然,这里要注意的是,一个 9 位二进制数 i 的范围是 [0, 8],而可选择的数字是 [1, 9],所以我们需要做一个映射,最简单的办法就是当我们知道 i 位置不为 0 的时候将 i + 1 加入子集。
  • 当然,子集枚举也可以用递归实现。在「官方题解 – 77. 组合」的方法一中提及了子集枚举递归实现的基本框架,感兴趣的同学可以参考。

复杂度分析

  1. 时间复杂度 O(M×2^M),其中 M 为集合的大小,本题中 M 固定为 9。一共有 2^M 个状态,每个状态需要 O(M + k) = O(M) 的判断(k \leq M),故时间复杂度为 O(M \times 2^M)
  2. 空间复杂度:O(M)。即 \rm temp 的空间代价。

编码实现

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

方法一:组合枚举

思路:

  • 我们可以换一个思路:我们需要在 9 个数中选择 k 个数,让它们的和为 n
  • 这样问题就变成了一个组合枚举问题。组合枚举有两种处理方法——递归法和字典序法,在「官方题解 – 77. 组合」中有详细的说明。
  • 这里我们要做的是做一个「在 9 个数中选择 k 个数」的组合枚举,对于枚举到的所有组合,判断这个组合内元素之和是否为 n。

复杂度分析

  1. 时间复杂度 O( M \choose k ×k),其中 M 为集合的大小,本题中 M 固定为 9。一共有 M \choose k 个组合,每次判断需要的时间代价是 O(k)
  2. 空间复杂度:O(M)temp 数组的空间代价是 O(k),递归栈空间的代价是 O(M),故空间复杂度为 O(M + k) = O(M)

编码实现

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:「手画图解」216. 组合总和 III

一句话解题

相似题目

编码实现

const combinationSum3 = (k, n) => {
  const res = []; 

  const dfs = (start, temp, sum) => {
    if (temp.length == k) {     // You've selected k numbers. End recursion
      if (sum == n) {           // The sum of numbers in a combination equals n
        res.push(temp.slice()); // Add its copy to the solution set
      }
      return;
    }
    for (let i = start; i <= 9; i++) { // Enumerate the options
      temp.push(i);                    // Make a choice
      dfs(i + 1, temp, sum + i);       // Explore
      temp.pop();                      // Undo the choice
    }
  };

  dfs(1, [], 0);  // press the search button
  return res;
};
US-B.Ralph
LeetCode数据结构与算法算法

Leave a Comment

邮箱地址不会被公开。 必填项已用*标注

7 + 3 =