[Link] https://leetcode.com/problems/combination-sum/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> list = new LinkedList<>();
dfs(list, new ArrayList<Integer>(), candidates, 0, target);
return list;
}
void dfs(List<List<Integer>> list, ArrayList<Integer> ll, int[] arr, int sIdx, int diff) {
if(diff == 0) {
list.add(new ArrayList<>( ll));
return;
}
for(int i = sIdx; i < arr.length; i++) {
if(diff < arr[i]) break;
ll.add(arr[i]);
dfs(list, ll, arr, i, diff - arr[i]);
ll.remove(ll.size() - 1);
}
}
}