-
Notifications
You must be signed in to change notification settings - Fork 1
/
CombinationSum.java
71 lines (60 loc) · 2.29 KB
/
CombinationSum.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
package com.leetcode;
import java.util.ArrayList;
import java.util.List;
public class CombinationSum {
//https://leetcode.com/problems/combination-sum/submissions/
//backtracking with sum passed as backtrack variable
/**
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Time complexity: O(2^n)
Space complexity: O(n)
**/
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> list = new ArrayList<>();
backtrack(0,0,target,candidates,list,result);
return result;
}
public void backtrack (int start,Integer sum,int target,int[] candidates,List<Integer> list,List<List<Integer>> result){
if(sum == target)
result.add(new ArrayList<>(list));
if(sum > target) return; // because no negative numbers.
for(int i = start ; i < candidates.length ; i++){
list.add(candidates[i]);
sum = sum+candidates[i];
backtrack(i,sum,target,candidates,list,result);
sum = sum-candidates[i];
list.remove(list.size()-1);
}
}
}
//backtracking with sum calculation at each level
class Solution2 {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> list = new ArrayList<>();
backtrack(0,target,candidates,list,result);
return result;
}
public void backtrack (int start,int target,int[] candidates,List<Integer> list,List<List<Integer>> result){
int sum = sumAll(list);
if( sum == target)
result.add(new ArrayList<>(list));
if(sum > target) return;
for(int i = start ; i < candidates.length ; i++){
list.add(candidates[i]);
backtrack(i,target,candidates,list,result);
list.remove(list.size()-1);
}
}
public int sumAll(List<Integer> list){
int sum = 0;
for(int i : list){
sum+= i;
}
return sum;
}
}
}