解题思路

题目要求在一个候选数组 candidates 中找到所有元素之和等于 target 的组合。每个数字在组合中只能使用一次，并且结果集不能包含重复的组合。

该问题的典型算法是 回溯法（Backtracking）。 核心思想如下：

1. 排序数组：先对 candidates 进行升序排序，方便后续去重与剪枝。

2. 回溯搜索：在递归过程中维护当前组合路径 path、当前和 sum、以及搜索起点 start。

3. 剪枝条件：

   • 若当前和 sum > target，则直接返回（因为数组已排序，后续只会更大）。
   • 若 sum == target，将当前组合加入结果集。

4. 去重策略：

   • 在同一层递归中（同一个起点的循环内），若遇到相同的数字（candidates[i] == candidates[i-1]），则跳过，防止重复组合。

此题是经典的「组合总和 II」问题（不同于组合总和 I，每个数字只能使用一次），因此递归下一层时的起点为 i+1 而非 i。

复杂度分析

• 时间复杂度：O(2ⁿ)，其中 n 为数组长度。最坏情况下需遍历所有子集。 但由于剪枝（排序+提前退出）和去重，实际远小于该上界。
• 空间复杂度：O(n)，主要来自递归调用栈与临时路径 path 的存储。

代码实现

Python

import sys

def dfs(a, start, target, path, ans):
    if target == 0:
        ans.append(path[:])
        return
    for i in range(start, len(a)):
        if i > start and a[i] == a[i - 1]:
            continue  # 同层去重
        if a[i] > target:
            break     # 剪枝
        path.append(a[i])
        dfs(a, i + 1, target - a[i], path, ans)  # 每个数只能用一次
        path.pop()

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    a = [int(next(it)) for _ in range(n)]
    target = int(next(it))

    a.sort()
    ans = []
    dfs(a, 0, target, [], ans)

    ans.sort()  # 字典序升序
    if not ans:
        print("")  # 按题意输出空行
        return
    out_lines = []
    for comb in ans:
        out_lines.append(" ".join(map(str, comb)))
    print("\n".join(out_lines))

if __name__ == "__main__":
    main()

C++

#include <bits/stdc++.h>
using namespace std;

void dfs(const vector<int>& a, int start, int target, vector<int>& path, vector<vector<int>>& ans) {
    if (target == 0) {
        ans.push_back(path);
        return;
    }
    for (int i = start; i < (int)a.size(); ++i) {
        if (i > start && a[i] == a[i - 1]) continue;    // 同层去重
        if (a[i] > target) break;                        // 剪枝
        path.push_back(a[i]);
        dfs(a, i + 1, target - a[i], path, ans);        // 每个数只能用一次
        path.pop_back();
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    int target; cin >> target;

    sort(a.begin(), a.end());
    vector<vector<int>> ans;
    vector<int> path;
    dfs(a, 0, target, path, ans);

    sort(ans.begin(), ans.end()); // 按字典序升序输出
    if (ans.empty()) {
        cout << "\n";
        return 0;
    }
    for (auto& v : ans) {
        for (int i = 0; i < (int)v.size(); ++i) {
            if (i) cout << ' ';
            cout << v[i];
        }
        cout << '\n';
    }
    return 0;
}

Java

import java.io.*;
import java.util.*;

public class Main {
    static void dfs(int[] a, int start, int target, List<Integer> path, List<List<Integer>> ans) {
        if (target == 0) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < a.length; i++) {
            if (i > start && a[i] == a[i - 1]) continue; // 同层去重
            if (a[i] > target) break;                    // 剪枝
            path.add(a[i]);
            dfs(a, i + 1, target - a[i], path, ans);     // 每个数只能用一次
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        Integer nObj = fs.nextInt();
        if (nObj == null) return;
        int n = nObj;
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = fs.nextInt();
        int target = fs.nextInt();

        Arrays.sort(a);
        List<List<Integer>> ans = new ArrayList<>();
        dfs(a, 0, target, new ArrayList<>(), ans);

        // 按字典序排序
        ans.sort((u, v) -> {
            int m = Math.min(u.size(), v.size());
            for (int i = 0; i < m; i++) {
                int cmp = Integer.compare(u.get(i), v.get(i));
                if (cmp != 0) return cmp;
            }
            return Integer.compare(u.size(), v.size());
        });

        if (ans.isEmpty()) {
            System.out.println();
            return;
        }
        StringBuilder sb = new StringBuilder();
        for (List<Integer> comb : ans) {
            for (int i = 0; i < comb.size(); i++) {
                if (i > 0) sb.append(' ');
                sb.append(comb.get(i));
            }
            sb.append('\n');
        }
        System.out.print(sb.toString());
    }

    // 轻量读入
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        Integer nextInt() throws IOException {
            String s = next();
            return s == null ? null : Integer.parseInt(s);
        }
        String next() throws IOException {
            StringBuilder sb = new StringBuilder();
            int c;
            while ((c = read()) != -1 && Character.isWhitespace(c));
            if (c == -1) return null;
            do { sb.append((char)c); } while ((c = read()) != -1 && !Character.isWhitespace(c));
            return sb.toString();
        }
    }
}

题目描述

给定一个候选数组 candidates（元素为非负整数）和一个目标数 target，找出所有和为 target 的不重复组合。 每个数字在每个组合中最多使用一次。结果中不包含重复组合，并按升序输出（组合内从小到大，所有组合按字典序升序）。

输入格式

• 第一行：整数 n（n ≥ 0），表示候选数个数。
• 第二行：n 个整数，表示 candidates。
• 第三行：整数 target。

输出格式

• 输出若干行，每行一个满足条件的组合，数之间用一个空格分隔；
• 若不存在可行解，输出空行（即打印一个空行）。

样例1

输入

7
10 1 2 7 6 1 5
8

输出

1 1 6
1 2 5
1 7
2 6

样例2

输入

5
2 5 2 1 2
5

输出

1 2 2
5