Day 26 of LeetCode

Documenting LeetCode solving.

Start to practice Java fluency.

Q80

46. Permutations

Medium. Backtracking

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> resultList = new ArrayList<>();
        backtrack(resultList, nums, new ArrayList<>());
        return resultList;
    }

    public void backtrack(List<List<Integer>> resultList, int[] nums, ArrayList<Integer> tempList) {   
        if (tempList.size() == nums.length) {
            // remember to new ArrayList<>(), otherwise its storing
            // a reference
            resultList.add(new ArrayList<>(tempList));
            return;
        }

        for (int num : nums) {
            // skip repeat num
            if (tempList.contains(num)){
                continue;
            }
            tempList.add(num);
            backtrack(resultList, nums, tempList);
            tempList.remove(tempList.size() - 1);
        }
    }

}

Q81

90. Subsets II

Medium.

class Solution {

    List<List<Integer>> resultList = new ArrayList<>();
    List<Integer> subset = new ArrayList<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        // sort to detect duplication
        Arrays.sort(nums);
        backtrack(0, nums);
        return resultList;
    }

    public void backtrack(int i, int[] nums) {
        if (i == nums.length) {
            resultList.add(new ArrayList<>(subset));
            return;
        }
        // include the current num
        subset.add(nums[i]);
        backtrack(i + 1, nums);
        subset.remove(subset.size() - 1);
        // exclude the current num and the num after with the same value
        while (i + 1 < nums.length && nums[i] == nums[i + 1]) {
            i++;
        }
        backtrack(i + 1, nums);

    }
}

Q82

40. Combination Sum II

Medium.

class Solution {

    List<List<Integer>> resultList = new ArrayList<>();
    ArrayList<Integer> track = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        backtrack(0, candidates, target);
        return resultList;
    }

    public void backtrack(int start, int[] candidates, int target) {
        if (target == 0) {
            resultList.add(new ArrayList<>(track));
            return;
        }
        if (target < 0) {
            return;
        }

        int prev = -1;
        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] == prev) {
                continue;
            }

            track.add(candidates[i]);
            backtrack(i + 1, candidates, target - candidates[i]);
            track.remove(track.size() - 1);
            prev = candidates[i];
        }
    }
}