Leetcode 39. Combination Sum
Explanation for Leetcode 39 - Combination Sum, and its solution in Python.
Problem
Example:
1
2
3
4
5
6
7
8
9
10
11
12
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.
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Input: candidates = [2], target = 1
Output: []
Approach
We can use DFS to find all the subsets but to optimize better, we can first sort the candidates to take the biggest out of the target.
Visualization of the Approach:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Input: candidates = [2,3,5], target = 8
[5,3,2]
/ \
[5] []
/ \ / \
[5,3] [5] [3] []
/ / \ /
[5,2] [3,3] [3] [2]
/ / /
[3,3,2] [3,2] [2,2]
/ /
[3,2,2] [2,2,2]
/
[2,2,2,2]
Thus, the only subset array that results total of 8 are [5,3], [3,3,2], [2,2,2,2]
Here is the Python code for the solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
candidates.sort(reverse=True)
def dfs(i, target, arr):
if target == 0:
res.append(arr)
return
if i == len(candidates):
return
if target >= candidates[i]:
dfs(i, target-candidates[i], arr+[candidates[i]])
dfs(i+1, target, arr)
dfs(0, target, [])
return res
Time Complexity and Space Complexity
Time Complexity: $O(2^n)$
Space Complexity: $O(n)$
This post is licensed under CC BY 4.0 by the author.