Combination Sum II
mediumRecursion & Backtracking+20 XPTime limit 2s
The numbers may contain duplicates, and each position may be used at most once. Find every distinct combination whose sum is exactly target.
Input:
- line 1:
n target - line 2:
npositive integers
Output: like Combination Sum — first the count c, then each combination on its own line in non-decreasing order, combinations in lexicographic order. No combination may appear twice.
Constraints: 1 ≤ n ≤ 100, 1 ≤ value ≤ 50, 1 ≤ target ≤ 30.
Think about it: sort, recurse with start k + 1 (each element once), and skip a[k] when it equals a[k−1] at the same depth — that removes duplicate combinations without a set.
Sample input 1
7 8 10 1 2 7 6 1 5
Sample output 1
4 1 1 6 1 2 5 1 7 2 6
Sample input 2
5 5 2 5 2 1 2
Sample output 2
2 1 2 2 5
Sample input 3
1 1 2
Sample output 3
0
📖 Stuck? Learn the pattern
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).