backtrack

Backtracking Leetcode Summary, Part 2

2019-10-22
  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
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    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:
    1
    2
    3
    4
    5
    6
    7
    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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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:

1
2
3
4
5
6
7
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:

1
2
3
4
5
6
7
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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:

1
2
3
4
5
6
7
8
9
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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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.

Backtracking Leetcode Summary, Part 1

2019-10-18
  1. N-Queens
  2. Permutation

N-Queens:

Problem Description: The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle. Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.
Thought Process in Short: Backtracking with DFS. We know each row has one queen, so we move from top line to the bottom line line by line, checking each column, and two diagonals.
Few Key Points:

  • For all “hill” diagonals row + column = const, and for all “dale” diagonals row - column = const.
  • There could be the only one queen in a row and the only one queen in a column.

Algorithms:

  1. Start from the first row = 0.
  2. Iterate over the columns and try to put a queen in each column.
    1. If square (row, column) is not under attack
      1. Place the queen in (row, column) square.
      2. Exclude one row, one column and two diagonals from further consideration.
      3. If all rows are filled up row == N
        • That means that we find out one more solution.
          Else
        • Proceed to place further queens backtrack(row + 1).
      4. Now backtrack : remove the queen from (row, column) square.

Codes:
Initialize log variables:

1
2
3
4
5
6
int rows[];
int hills[];
int dales[];
int n;
List<List<String>> output = new ArrayList();
int queens[];

Checking if a cell is under attack:

1
2
3
4
5
6
7
8
public boolean isNotUnderAttack(int row, int col) {
    int res = rows[col] + hills[row - col + 2 * n] + dales[row + col];
    if (res == 0) {
        return true;
    } else {
        return false;
    }
}

Method placing and removing queens:

1
2
3
4
5
6
7
8
9
10
11
12
13
public void placeQueen(int row, int col) {
    queens[row] = col;
    rows[col] = 1;
    hills[row - col + 2 * n] = 1;
    dales[row + col] = 1;
}

public void removeQueen(int row, int col) {
    queens[row] = 0;
    rows[col] = 0;
    hills[row - col + 2 * n] = 0;
    dales[row + col] = 0;
}

Adding a solution to existing solutions:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void addSolution() {
    List<String> solution = new ArrayList<String>();
    for (int i = 0; i < n; ++i) {
        int col = queens[i];
        StringBuilder sb = new StringBuilder();
        for (int j = 0; j < col; ++j) {
            sb.append(".");
        }
        sb.append("Q");
        for (int j = 0; j < n - col - 1; ++j) {
            sb.append(".");
        }
        solution.add(sb.toString());
    }
    output.add(solution);
}

The actual backtracking process:

1
2
3
4
5
6
7
8
9
10
11
12
13
public void backtrack (int row) {
    for (int col = 0; col < n; col++) {
        if (isNotUnderAttack(row, col)) {
            placeQueen(row, col);
            if (row + 1 == n) {
                addSolution();
            } else {
                backtrack(row + 1);
            }
            removeQueen(row, col);
        }
    }
}

Main function of solution:

1
2
3
4
5
6
7
8
9
10
public List<List<String>> solveNQueens(int n) {
    this.n = n;
    rows = new int[n];
    hills = new int[4 * n - 1];
    dales = new int[2 * n - 1];
    queens = new int[n];
    
    backtrack(0);
    return output;
}

Permutation:

One of the more basic backtracking problem.
Algorithms:

  1. If the first integer to consider has index n that means that the current permutation is done.
  2. Iterate over the integers from index first to index n - 1.
    1. Place i-th integer first in the permutation, i.e. swap(nums[first], nums[i]).
    2. Proceed to create all permutations which starts from i-th integer : backtrack(first + 1).
    3. Now backtrack, i.e. swap(nums[first], nums[i]) back.

Code：
BFS to find solutions, then backtracking to reverse to previous states. The following is the backtracking part.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void backtrack(int n, 
                      ArrayList<Integer> nums, 
                      List<List<Integer>> res, 
                      int first_idx) {
    if (first_idx == n) {
        res.add(new ArrayList<Integer>(nums));
    }
    for (int i = first_idx; i < n; i++) {
        # swap first and ith
        Collections.swap(nums, first_idx, i);
        backtrack(n, nums, res, first_idx+1);
        # swap back to original
        Collections.swap(nums, first_idx, i);
    }
}

Main function of solution:

1
2
3
4
5
6
7
8
9
10
public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new LinkedList();
    ArrayList<Integer> nums_list = new ArrayList<Integer>();
    for (int num : nums) {
        nums_list.add(num);
    }
    int n = nums.length;
    backtrack(n, nums_list, res, 0);
    return res;
}
© 2020 ZEXI JIN - Powered by Hexo - Theme Chan