解题思路
题目要求在一个候选数组 candidates 中找到所有元素之和等于 target 的组合。每个数字在组合中只能使用一次,并且结果集不能包含重复的组合。
该问题的典型算法是 回溯法(Backtracking)。
核心思想如下:
- 排序数组:先对
candidates 进行升序排序,方便后续去重与剪枝。
- 回溯搜索:在递归过程中维护当前组合路径
path、当前和 sum、以及搜索起点 start。
P4295.第2题-候选人编号
题目描述
给定一个候选数组 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