Skip to content

Instantly share code, notes, and snippets.

@darkcar
Created June 12, 2019 04:34
Show Gist options
  • Save darkcar/9360f0de3f71777912a448e8153e8541 to your computer and use it in GitHub Desktop.
Save darkcar/9360f0de3f71777912a448e8153e8541 to your computer and use it in GitHub Desktop.
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
// Sort candidates
Arrays.sort(candidates); // Time complexity: O(nlogn)
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> eachSolution = new ArrayList<Integer>();
for(int i = 0; i < candidates.length; i ++) {
if(target % candidates[i] == 0) {
for(int j = 0; j < target / candidates[i]; j ++) {
eachSolution.add(candidates[i]);
}
}
}
int size = candidates.length;
int[][] board = new int[size][size];
for(int i = size - 1; i >= 0; i --) {
for(int j = 0; j < size; j ++) {
int tempSum = candidates[i] + candidates[j];
if(tempSum > target) {
board[i][j] = -1;
} else {
board[i][j] = tempSum;
}
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment