leetcode-algorithms/src/CombinationSumII.java at master · anishLearnsToCode/leetcode-algorithms · GitHub

39 lines (33 loc) · 1.23 KB

// https://leetcode.com/problems/combination-sum-ii

// T: O(2^N)

// S: O(N)

import java.util.ArrayList;

import java.util.Arrays;

import java.util.LinkedList;

import java.util.List;

public class CombinationSumII {

public List<List<Integer>> combinationSum2(int[] candidates, int target) {

List<List<Integer>> results = new ArrayList<>();

LinkedList<Integer> comb = new LinkedList<>();

Arrays.sort(candidates);

backtrack(candidates, comb, target, 0, results);

return results;

}

private void backtrack(int[] candidates, LinkedList<Integer> comb,

int remain, int curr,

List<List<Integer>> results) {

if (remain == 0) {

results.add(new ArrayList<Integer>(comb));

return;

}

for (int nextCurr = curr; nextCurr < candidates.length; ++nextCurr) {

if (nextCurr > curr && candidates[nextCurr] == candidates[nextCurr - 1])

continue;

int pick = candidates[nextCurr];

if (remain - pick < 0) break;

comb.addLast(pick);

backtrack(candidates, comb, remain - pick, nextCurr + 1, results);

comb.removeLast();

}

Expand file tree