Backtracking Leetcode Summary, Part 2

1. Subsets
2. Palindrome
3. Combination Sum, repeated number used
4. Combination Sum, unique number used

Subsets:

Problem Description: Given a set of distinct integers, nums, return all possible subsets (the power set). Note: The solution set must not contain duplicate subsets.
Few Key Points:

• This algorithm is very close to that of permutation. The only difference is that this counts for subsets instead of permutations.
• One of the key point is to keep the order, don’t permute like the permutation algorithm

Code:
backtracking part, takes parameters:

• result: LinkedList>
• current: ArrayList
• nums: nums to extract from
• cur_idx: current index
  Note: when adding to result, convert the current list into a new list

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

  The solution part:

  public List<List<Integer>> subsets(int[] nums) {
      List<List<Integer>> res = new LinkedList<>();
      List<Integer> tmp = new ArrayList<Integer>();
      int start = 0;
      backtrack(res, tmp, nums, start);
      return res;
  }

Palindrome:

Problem Description: Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
e.g.:
Input: “aab”
Output:
[[“aa”,”b”],
[“a”,”a”,”b”]]
Few Key Points:
An utility function can be used to determine if str is palindrome or not.
Code:
backtrack:

public void backtrack(List<List<String>> result, 
                      List<String> tmp, 
                      String str, 
                      int index) {
    if (index == str.length()) 
        result.add(new ArrayList<String>(tmp));
    else {
        for (int i = index; i < str.length(); i++) {
            if (isPalindrome(str, index, i)) {
                tmp.add(str.substring(index, i+1));
                backtrack(result, tmp, str, i+1);
                tmp.remove(tmp.size()-1);
            }
        }
    }
}

Check if str is palindrome:

public boolean isPalindrome(String str, int s, int e) {
    while (s < e) {
        if (str.charAt(s++) != str.charAt(e--))
            return false;
    }
    return true;
}

The solution part:

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

Combination Sum, repeat allowed

Problem Description: Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. The same repeated number may be chosen from candidates unlimited number of times.
e.g.:
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[[7],
[2,2,3]]
Codes:
backtrack:

public void backtrack(List<List<Integer>> res, 
                 List<Integer> tmp, 
                 int[] cand, 
                 int rem, 
                 int cur) {
    if (rem == 0) {
        res.add(new ArrayList<Integer>(tmp));
    } else if (rem < 0) {
        return;
    } else {
        for (int i = cur; i < cand.length; i++) {
            if (rem >= cand[i]) {
                tmp.add(cand[i]);
                backtrack(res, tmp, cand, rem - cand[i], i);
                tmp.remove(tmp.size()-1);
            } else {
                break;
            }
        }
    }
}

The solution part:

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> res = new LinkedList<>();
    List<Integer> tmp = new ArrayList<Integer>();
    int cur = 0;
    int rem = target;
    Arrays.sort(candidates);
    backtrack(res, tmp, candidates, rem, cur);
    return res;
}

Combination Sum, no repeats

Problem Description: Same as combination sum, with only difference that each number can only be used once.

Codes:
backtrack: (added while loop to eliminate repeating results)

public void backtrack(List<List<Integer>> res, 
                 List<Integer> tmp, 
                 int[] cand, 
                 int rem, 
                 int cur) {
    if (rem == 0) {
        res.add(new ArrayList<Integer>(tmp));
    } else if (rem < 0) {
        return;
    } else {
        for (int i = cur; i < cand.length; i++) {
            if (rem >= cand[i]) {
                tmp.add(cand[i]);                    
                backtrack(res, tmp, cand, rem - cand[i], i+1);
                tmp.remove(tmp.size()-1);
                while (i < cand.length-1 && cand[i] == cand[i+1])
                    i += 1;
            } else {
                break;
            }
        }
    }
}

The solution part is the same as the last section.