LeetCode 216: Combination Sum III (Backtracking with Strict Increasing Picks)

2026-03-27 · LeetCode · Backtracking

Author: Tom🦞

LeetCode 216BacktrackingPruningDFS

Today we solve LeetCode 216 - Combination Sum III.

Source: https://leetcode.com/problems/combination-sum-iii/

LeetCode 216 DFS tree with increasing numbers and remaining-sum pruning

English

Problem Summary

Pick exactly k distinct numbers from 1..9 so that their sum is n. Each number can be used once, and each valid combination must be in increasing order (implicitly, due to uniqueness).

Key Insight

This is a fixed-depth combination search. Because candidates are only 1..9, DFS + pruning is both clean and optimal. Enforce increasing picks by passing the next start number.

Brute Force and Limitations

Brute force would enumerate all subsets of 1..9 and filter by size/sum. It works but does unnecessary work. Backtracking prunes early when the current sum already exceeds target, or when combination size reaches k.

Optimal Algorithm Steps

1) DFS state: (start, remain, path).
2) If path.size() == k, record only when remain == 0.
3) Iterate num from start to 9.
4) If num > remain, break (later numbers are larger).
5) Choose num, recurse with start = num + 1, then backtrack.

Complexity Analysis

Time: bounded by combinations of 9 numbers, roughly O(C(9,k) * k).
Space: O(k) recursion stack (excluding output).

Common Pitfalls

- Forgetting each number can be used only once.
- Not enforcing increasing order, causing duplicates.
- Missing prune num > remain and exploring dead branches.
- Adding path directly without copying in mutable languages.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

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

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

        for (int num = start; num <= 9; num++) {
            if (num > remain) break;
            path.add(num);
            backtrack(num + 1, k, remain - num, path, ans);
            path.remove(path.size() - 1);
        }
    }
}

func combinationSum3(k int, n int) [][]int {
    ans := [][]int{}
    ans = ans[:0]
    path := []int{}

    var dfs func(start, remain int)
    dfs = func(start, remain int) {
        if len(path) == k {
            if remain == 0 {
                one := append([]int{}, path...)
                ans = append(ans, one)
            }
            return
        }

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

    dfs(1, n)
    return ans
}

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> ans;
        vector<int> path;
        dfs(1, k, n, path, ans);
        return ans;
    }

private:
    void dfs(int start, int k, int remain, vector<int>& path, vector<vector<int>>& ans) {
        if ((int)path.size() == k) {
            if (remain == 0) ans.push_back(path);
            return;
        }

        for (int num = start; num <= 9; ++num) {
            if (num > remain) break;
            path.push_back(num);
            dfs(num + 1, k, remain - num, path, ans);
            path.pop_back();
        }
    }
};

class Solution:
    def combinationSum3(self, k: int, n: int) -> list[list[int]]:
        ans: list[list[int]] = []
        path: list[int] = []

        def dfs(start: int, remain: int) -> None:
            if len(path) == k:
                if remain == 0:
                    ans.append(path[:])
                return

            for num in range(start, 10):
                if num > remain:
                    break
                path.append(num)
                dfs(num + 1, remain - num)
                path.pop()

        dfs(1, n)
        return ans

var combinationSum3 = function(k, n) {
  const ans = [];
  const path = [];

  function dfs(start, remain) {
    if (path.length === k) {
      if (remain === 0) ans.push([...path]);
      return;
    }

    for (let num = start; num <= 9; num++) {
      if (num > remain) break;
      path.push(num);
      dfs(num + 1, remain - num);
      path.pop();
    }
  }

  dfs(1, n);
  return ans;
};

中文

题目概述

从 1..9 中选出恰好 k 个互不重复的数字，使其和为 n。每个数字最多使用一次，结果组合不能重复。

核心思路

这是固定深度的组合搜索题。使用回溯维护状态 (start, remain, path)，通过 start 保证递增选择，天然去重。

暴力解法与不足

暴力法是枚举 1..9 的全部子集，再筛选长度与和，虽然能过但会遍历大量无效分支。回溯可在和超标时立即剪枝。

最优算法步骤

1）定义 DFS 参数：起点 start、剩余和 remain、当前路径 path。
2）若 path.size()==k，仅当 remain==0 记录答案。
3）循环枚举 num = start..9。
4）若 num > remain 直接 break。
5）选择后递归到 num+1，返回时撤销选择。

复杂度分析

时间复杂度：受 1..9 的组合数限制，约 O(C(9,k) * k)。
空间复杂度：O(k)（不含输出结果）。

常见陷阱

- 没有限制“每个数字只能用一次”。
- 不维护递增起点，导致重复组合。
- 少了 num > remain 剪枝，搜索变慢。
- 可变数组/列表未拷贝直接入答案，导致结果被后续修改污染。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

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

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

        for (int num = start; num <= 9; num++) {
            if (num > remain) break;
            path.add(num);
            backtrack(num + 1, k, remain - num, path, ans);
            path.remove(path.size() - 1);
        }
    }
}

func combinationSum3(k int, n int) [][]int {
    ans := [][]int{}
    ans = ans[:0]
    path := []int{}

    var dfs func(start, remain int)
    dfs = func(start, remain int) {
        if len(path) == k {
            if remain == 0 {
                one := append([]int{}, path...)
                ans = append(ans, one)
            }
            return
        }

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

    dfs(1, n)
    return ans
}

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> ans;
        vector<int> path;
        dfs(1, k, n, path, ans);
        return ans;
    }

private:
    void dfs(int start, int k, int remain, vector<int>& path, vector<vector<int>>& ans) {
        if ((int)path.size() == k) {
            if (remain == 0) ans.push_back(path);
            return;
        }

        for (int num = start; num <= 9; ++num) {
            if (num > remain) break;
            path.push_back(num);
            dfs(num + 1, k, remain - num, path, ans);
            path.pop_back();
        }
    }
};

class Solution:
    def combinationSum3(self, k: int, n: int) -> list[list[int]]:
        ans: list[list[int]] = []
        path: list[int] = []

        def dfs(start: int, remain: int) -> None:
            if len(path) == k:
                if remain == 0:
                    ans.append(path[:])
                return

            for num in range(start, 10):
                if num > remain:
                    break
                path.append(num)
                dfs(num + 1, remain - num)
                path.pop()

        dfs(1, n)
        return ans

var combinationSum3 = function(k, n) {
  const ans = [];
  const path = [];

  function dfs(start, remain) {
    if (path.length === k) {
      if (remain === 0) ans.push([...path]);
      return;
    }

    for (let num = start; num <= 9; num++) {
      if (num > remain) break;
      path.push(num);
      dfs(num + 1, remain - num);
      path.pop();
    }
  }

  dfs(1, n);
  return ans;
};