Combination Sum
Medium
Difficulty
O(2^n)
Time Complexity
O(n)
Space Complexity
Backtracking
Approach
Jan 27, 2026
Last Updated
Problem Statement
Given an array of distinct integers
The same number may be chosen from
The test cases are generated such that the number of unique combinations that sum up to
candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.
The same number may be chosen from
candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.
The test cases are generated such that the number of unique combinations that sum up to
target is less than 150 combinations for the given input.
Examples
Example 1:
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation: 2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times. 7 is a candidate, and 7 = 7. These are the only two combinations.
Example 2:
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Example 3:
Input: candidates = [2], target = 1
Output: []
Backtracking Approach
Backtracking Approach
1class Solution {
2
3 List<List<Integer>> list = new ArrayList<>();
4 public List<List<Integer>> combinationSum(int[] nums, int target) {
5 List<Integer> bits = new ArrayList<>();
6 combos(0, nums, 0, target, bits);
7 return list;
8 }
9
10 public void combos(int n, int[] nums, int sum, int target, List<Integer> bits){
11
12 // base case
13 if (sum == target){
14 list.add(new ArrayList<>(bits));
15 return;
16 }
17 if (sum > target){
18 return;
19 }
20 if (n == nums.length){
21 return;
22 }
23
24 // repeat
25 int newSum = sum + nums[n];
26 if (newSum >= sum && newSum <= target){
27 bits.add(nums[n]);
28 combos(n, nums, newSum, target, bits);
29 bits.remove(bits.size()-1);
30 }
31
32 // dont repeat
33 combos(n+1, nums, sum, target, bits);
34 }
35}
36