LeetCode 216. 组合总和 III（组合型枚举）

文章目录

• LeetCode、216. 组合总和 III【中等，组合型枚举】
• 题目类型与分类
• 思路

LeetCode、216. 组合总和 III【中等，组合型枚举】

题目类型与分类

题目链接：LeetCode、216. 组合总和 III

题目类型：搜索与图论/回溯、基础算法/枚举（组合型枚举，n个数中取m个）

---

思路

思路描述：组合型枚举+选中的符合条件的情况案例

组合型模板直接套上，然后对选中的几个位置（state数组元素不为0的）求下和看是否是目标值，若是的话将这条情况添加到结果集中。

中间过程对于在1-9中是否选中，我们根据一个state数组来进行表示。

复杂度分析：时间复杂度O(m^n^!)，空间复杂度O(1)

import java.util.ArrayList;
import java.util.List;

class Solution {

    public int n, m;
    public int[] state;//若为0表示没有选中，不为0表示选中
    public List<List<Integer>> res;

    //组合型枚举，n个数中取m个
    //本题为：1-9中取k个，和为n
    public List<List<Integer>> combinationSum3(int k, int sum) {
        //表示从9个中选k个
        this.n = 9;
        this.m = k;
        this.state = new int[n];
        this.res = new ArrayList<>();
        dfs (0, 0, sum);
        return res;
    }

    /**
     * @param u 总计达到k个（取的k个数量）
     * @param start 当前应当开始的位置
     */
    public void dfs (int u, int start, int sum) {
        //提前剪枝
        //u表示当前取了几个  n - start表示还有几个未取
        //若是两个相加不满足我们最终要取的个数，那么直接结束
        if (u + (n - start) < m) return;
        //若是刚好已经取到了m个
        if (u == m) {
            List<Integer> choice = new ArrayList<>();
            int s = 0;
            for (int i = 0; i < n; i++) {
                if (state[i] != 0) {
                    s += state[i];
                    choice.add(state[i]);
                }
            }
            if (s == sum) {
                res.add(choice);
            }
        }
        for (int i = start; i < n; i ++) {
            state[i] = i + 1;
            dfs (u + 1, i + 1, sum);
            state[i] = 0;
        }
    }


}

---

整理者：长路 时间：2024.1.31