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
- 1 ≤ n ≤ 30
- 1 ≤ candidate ≤ 200
- 1 ≤ target ≤ 500
Example 1
Input
4 2 3 6 7 7
Output
2
Example 2
Input
3 2 3 5 8
Output
3
Hints
- 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).
- 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]);
}
}