Practice › Recursion & Backtracking
Combination Sum II
Medium · Recursion & Backtracking · Asked at Amazon, Microsoft, Meta, Adobe
Find all distinct combinations of the candidates that sum to target. Each candidate may be used at most once (but the list may contain equal numbers). Print the number of combinations, then each combination on its own line with elements in increasing order, combinations sorted lexicographically.
Input
First line: n target. Second line: the n candidates.
Output
The count, then the combinations (only the count if it is 0).
Constraints
- 1 ≤ n ≤ 30
- 1 ≤ candidates[i] ≤ 50
- 1 ≤ target ≤ 40
Sort, then backtrack; skip a candidate equal to the previous one at the same recursion level, and stop early once the candidate exceeds the remaining target.
Example 1
Input
7 8 10 1 2 7 6 1 5
Output
4 1 1 6 1 2 5 1 7 2 6
Example 2
Input
5 5 2 5 2 1 2
Output
2 1 2 2 5
Hints
- Sort the candidates. Each one can be used once, so after choosing index i the next choice starts at i + 1.
- Skip a candidate equal to the previous one at the same level, and stop the loop as soon as a candidate is bigger than the remaining target.
Approach
go(start, rem, cur): if rem == 0, record cur. Otherwise loop i from start; break when a[i] > rem (the array is sorted, so later ones are bigger too); skip a[i] if i > start and it equals a[i−1]; otherwise choose it and recurse with i + 1. The combinations are produced in lexicographic order, each exactly once.
Complexity: O(2^n · n) worst case, heavily pruned · O(n) recursion depth
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
vector<int> a, cur;
vector<string> out;
void go(int start, int rem) {
if (rem == 0) {
string s;
for (size_t i = 0; i < cur.size(); i++) s += (i ? " " : "") + to_string(cur[i]);
out.push_back(s);
return;
}
for (int i = start; i < (int)a.size() && a[i] <= rem; i++) {
if (i > start && a[i] == a[i - 1]) continue;
cur.push_back(a[i]);
go(i + 1, rem - a[i]);
cur.pop_back();
}
}
int main() {
int n, t;
cin >> n >> t;
a.resize(n);
for (auto &x : a) cin >> x;
sort(a.begin(), a.end());
go(0, t);
cout << out.size() << "\n";
for (auto &s : out) cout << s << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n, t = data[0], data[1]
a = sorted(data[2 : 2 + n])
out = []
def go(start, rem, cur):
if rem == 0:
out.append(" ".join(map(str, cur)))
return
for i in range(start, n):
if a[i] > rem:
break
if i > start and a[i] == a[i - 1]:
continue
go(i + 1, rem - a[i], cur + [a[i]])
go(0, t, [])
print(len(out))
if out:
print("\n".join(out))Java solution
import java.util.*;
public class Main {
static int[] a;
static List<String> out = new ArrayList<>();
static Deque<Integer> cur = new ArrayDeque<>();
static void go(int start, int rem) {
if (rem == 0) {
StringBuilder sb = new StringBuilder();
for (int x : cur) sb.append(sb.length() > 0 ? " " : "").append(x);
out.add(sb.toString());
return;
}
for (int i = start; i < a.length && a[i] <= rem; i++) {
if (i > start && a[i] == a[i - 1]) continue;
cur.addLast(a[i]);
go(i + 1, rem - a[i]);
cur.removeLast();
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), t = sc.nextInt();
a = new int[n];
for (int i = 0; i < n; i++) a[i] = sc.nextInt();
Arrays.sort(a);
go(0, t);
StringBuilder sb = new StringBuilder();
sb.append(out.size()).append('\n');
for (String s : out) sb.append(s).append('\n');
System.out.print(sb);
}
}