LeetCode 216. 组合总和 III

Categories:

题目描述
思路分析
1. 解法一：回溯剪枝（推荐）
相似题目

题目描述

✅ 216. 组合总和 III

思路分析

解法一：回溯剪枝（推荐）

核心思路：

在 1 到 9 中选择 k 个数使其和为 n。

采用回溯枚举，递增选择，避免重复。

当剩余数字不足或和已超时及时剪枝。

复杂度分析：

时间复杂度：O(C(9, k))，枚举所有组合。

空间复杂度：O(k)，递归栈与路径存储。

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

class Solution {
    private final List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> combinationSum3(int k, int n) {
        backtrack(1, k, n, new ArrayList<>());
        return res;
    }

    private void backtrack(int start, int k, int target, List<Integer> path) {
        if (path.size() == k) {
            if (target == 0) {
                res.add(new ArrayList<>(path));
            }
            return;
        }

        for (int i = start; i <= 9; i++) {
            if (target - i < 0) {
                break;
            }

            path.add(i);
            backtrack(i + 1, k, target - i, path);
            path.remove(path.size() - 1);
        }
    }
}

func combinationSum3(k int, n int) [][]int {
	res := make([][]int, 0)
	path := make([]int, 0, k)

	var dfs func(start, remain int)
	dfs = func(start, remain int) {
		if len(path) == k {
			if remain == 0 {
				tmp := make([]int, k)
				copy(tmp, path)
				res = append(res, tmp)
			}
			return
		}

		for i := start; i <= 9; i++ {
			if remain-i < 0 {
				break
			}
			path = append(path, i)
			dfs(i+1, remain-i)
			path = path[:len(path)-1]
		}
	}

	dfs(1, n)
	return res
}

相似题目

题目	难度	考察点
39. 组合总和	中等	回溯
40. 组合总和 II	中等	回溯
77. 组合	中等	回溯
78. 子集	中等	回溯
90. 子集 II	中等	回溯

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/88462841