Getting everything ready for you…

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

0s

Practice › Recursion & Backtracking

Combination Sum Count

Medium · Recursion & Backtracking · Asked at Amazon, Microsoft, Uber, Adobe

Given distinct positive candidates and a target, count the combinations whose sum is the target. Each candidate may be used any number of times; combinations differing only in order count once.

Input

First line: n. Second line: n distinct integers. Third line: target.

Output

The number of combinations.

Constraints

Example 1

Input

4
2 3 6 7
7

Output

2

Example 2

Input

3
2 3 5
8

Output

3

Hints

  1. To avoid counting [2,3,2] and [2,2,3] separately, only allow candidates in a fixed order (never go back to an earlier one).
  2. This is "coin change — number of ways": dp[v] += dp[v − c], looping over candidates in the outer loop.

Approach

Backtracking with a start index works: at each step choose candidate i or a later one, which means each multiset is built in a single order. Its DP form is shorter: dp[0] = 1, and for each candidate c (outer loop), for v from c to target, dp[v] += dp[v − c]. With candidates in the outer loop, every combination is counted once, in candidate order. Swapping the loops would count orderings instead.

Complexity: O(n · target) time · O(target) space

Solution

C++ solution

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

int main() {
    int n, target;
    cin >> n;
    vector<int> c(n);
    for (auto &x : c) cin >> x;
    cin >> target;
    vector<long long> dp(target + 1, 0);
    dp[0] = 1;
    for (int x : c)
        for (int v = x; v <= target; v++) dp[v] += dp[v - x];
    cout << dp[target] << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
n = data[0]
cands, target = data[1 : n + 1], data[n + 1]
dp = [1] + [0] * target
for c in cands:
    for v in range(c, target + 1):
        dp[v] += dp[v - c]
print(dp[target])

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] c = new int[n];
        for (int i = 0; i < n; i++) c[i] = sc.nextInt();
        int target = sc.nextInt();
        long[] dp = new long[target + 1];
        dp[0] = 1;
        for (int x : c)
            for (int v = x; v <= target; v++) dp[v] += dp[v - x];
        System.out.println(dp[target]);
    }
}

Solve Combination Sum Count online · All practice problems