Backtrack

https://leetcode.com/problems/combination-sum/discuss/16502/

In Leetcode, there are many backTrack problems, some of which are good starting points.

[x] Combination Sum,
[x] Factor Combinations,
[x] Permutations,
[x] Permutations II.
[ ] More advanced:
[ ] Evaluate Division,
[ ] Word Pattern II,
[ ] Remove Invalid Parentheses,
[ ] Basic Calculator

When solving a BT problem, pay attention to whether it’s a Permutation problem, or a Combination.

The problem here is a permutation.

This structure might apply to many other backtracking questions, but here I am just going to demonstrate Subsets, Permutations, and Combination Sum.

1-39.Combination Sum

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        helper(ans, new ArrayList<>(), candidates, 0, 0, target);
        return ans;
    }

    public void helper(List<List<Integer>> ans, List<Integer> comb, int[] candidates, int curPos, int curSum, int target){
        if(curSum > target)
            return ;
        if(curSum == target){
            //comb.add(candidates[curPos]);
            ans.add(new ArrayList<>(comb));
            return;
        }
        else{
            for(int i = curPos; i < candidates.length; i++){
                comb.add(candidates[i]);
                helper(ans, comb, candidates, i,  curSum + candidates[i], target);
                comb.remove(comb.size() - 1);
            }
            return;
        }
    }
}

40.Combination Sum II

class Solution {
    public List<List<Integer>> combinationSum2(int[] nums, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        helper(ans, new ArrayList<>(), nums, target, 0);
        return ans;
    }
    public void helper(List<List<Integer>> ans, List<Integer> comb, int[] nums, int target, int start){
        if(target < 0)
            return;
        if(target == 0){
            ans.add(new ArrayList<>(comb));
            return;
        }
        else{
            for(int i = start; i < nums.length; i++){
                if(i > start && nums[i] == nums[i-1])
                    continue;
                else{
                    comb.add(nums[i]);
                    helper(ans, comb, nums, target - nums[i], i + 1);
                    comb.remove(comb.size() - 1);
                }
            }
            return;
        }
    }
}

2-78.Subsets

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        helper(ans, new ArrayList<>(), nums, 0);
        return ans;
    }

    public void helper(List<List<Integer>> ans, List<Integer> comb, int[] nums, int start){
        ans.add(new ArrayList<>(comb));
        for(int i = start; i < nums.length; i++){
            comb.add(nums[i]);
            helper(ans, comb, nums, i + 1);
            comb.remove(comb.size() - 1);
        }
        return;
    }
}

90.Subsets II

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        helper(ans, new ArrayList<>(), nums, 0);
        return ans;
    }

    public void helper(List<List<Integer>> ans,  List<Integer> comb, int[] nums, int start){
        ans.add(new ArrayList<>(comb));
        for(int i = start; i < nums.length; i++){
            if(i != start && nums[i] == nums[i - 1])
                continue;
            comb.add(nums[i]);
            helper(ans, comb, nums, i + 1);
            comb.remove(comb.size() - 1);
        }
        return;
    }
}

46.Permutations

public List<List<Integer>> permute(int[] nums) {
   List<List<Integer>> list = new ArrayList<>();
   // Arrays.sort(nums); // not necessary
   backtrack(list, new ArrayList<>(), nums);
   return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){
   if(tempList.size() == nums.length){
      list.add(new ArrayList<>(tempList));
   } else{
      for(int i = 0; i < nums.length; i++){ 
         if(tempList.contains(nums[i])) continue; // element already exists, skip
         tempList.add(nums[i]);
         backtrack(list, tempList, nums);
         tempList.remove(tempList.size() - 1);
      }
   }
}

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

    public void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
        return;
    }
    public void helper(List<List<Integer>> ans, int[] nums, int start){
        if(start == nums.length){
            List<Integer> comb = new ArrayList<>();
            for(int i : nums){
                comb.add(i);
            }
            ans.add(comb);
        }
        else{
            for(int i = start; i < nums.length; i++){
                swap(nums, i, start);
                helper(ans, nums, start + 1);
                swap(nums, i, start);
            }
        }
        return;
    }
}

47 Permutations II

Diff: Use Set to Avoid Duplicate

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        helper(ans, nums, 0);
        return ans;
    }
    public void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
        return;
    }
    public void helper(List<List<Integer>> ans, int[] nums, int start){
        if(start == nums.length){
            List<Integer> comb = new ArrayList<>();
            for(int i : nums){
                comb.add(i);
            }
            ans.add(comb);
        }
        else{
            Set<Integer> set = new HashSet<>();
            for(int i = start; i < nums.length; i++){
                if(!set.contains(nums[i])){
                    set.add(nums[i]);
                    swap(nums, i, start);
                    helper(ans, nums, start + 1);
                    swap(nums, i, start);
                }                
            }
        }
        return;
    }
}

131.Palindrome Partitioning

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> ans = new ArrayList<>();
        helper(ans, new ArrayList<>(), s);
        return ans;
    }
    public boolean isPalindrome(String s){
        boolean res = true;
        int i = 0;
        int j = s.length() - 1;
        while(i <= j){

            if(s.charAt(i) != s.charAt(j)){
                res = false;
                break;
            }
            i++;
            j--;
        }
        return res;
    }
    public void helper(List<List<String>> ans, List<String> comb, String s){
        if(s.length() < 1){
            ans.add(new ArrayList<>(comb));
            return;
        }
        else{
            for(int i = 1; i <= s.length(); i++){
                String s1 = s.substring(0, i);
                if(!isPalindrome(s1))
                    continue;
                else{
                    comb.add(s1);
                    helper(ans, comb, s.substring(i));
                    comb.remove(comb.size() - 1);
                }
            }
            return;
        }
    }
}


public List<List<String>> partition(String s) {
   List<List<String>> list = new ArrayList<>();
   backtrack(list, new ArrayList<>(), s, 0);
   return list;
}

public void backtrack(List<List<String>> list, List<String> tempList, String s, int start){
   if(start == s.length())
      list.add(new ArrayList<>(tempList));
   else{
      for(int i = start; i < s.length(); i++){
         if(isPalindrome(s, start, i)){
            tempList.add(s.substring(start, i + 1));
            backtrack(list, tempList, s, i + 1);
            tempList.remove(tempList.size() - 1);
         }
      }
   }
}

public boolean isPalindrome(String s, int low, int high){
   while(low < high)
      if(s.charAt(low++) != s.charAt(high--)) return false;
   retu

254.Factor Combinations

class Solution {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> ans = new ArrayList<>();
        helper(ans, new ArrayList<>(), n, 2);
        return ans;
    }
    public void helper(List<List<Integer>> ans, List<Integer> comb, int n, int start){
        if(n == 1){
            if(comb.size() > 1)
                ans.add(new ArrayList<>(comb));
            return;
        }
        else{
            for(int i = start; i <= n; i++){
                if(n % i == 0){
                    comb.add(i);
                    helper(ans, comb, n / i, i);
                    comb.remove(comb.size() - 1);
                }
            }
            return;
        }
    }
}

Backtracking