Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Sort the candidates. Each one can be used once, so after choosing index i the next choice starts at i + 1.
  2. 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);
    }
}

Solve Combination Sum II online · All practice problems