Leetcode-Backtracking

Reference: Link

17. Letter Combinations of a Phone Number (Medium)

This problem is not difficult. We iterate all possible letters and backtrack to find all possible combinations.

Time complexity : O(3^N×4^M) where N is the number of digits in the input that maps to 3 letters (e.g. 2, 3, 4, 5, 6, 8) and M is the number of digits in the input that maps to 4 letters (e.g. 7, 9), and N+M is the total number digits in the input. Space complexity : O(3^N×4^M). since one has to keep O(3^N×4^M) solutions. Here is the link.

private static final String[] KEYS = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
public List<String> letterCombinations(String digits) {

    List<String>ans = new ArrayList();
    if(digits.length()==0)return ans;
    backtrack(digits,ans,"");
    return ans;
}

public void backtrack(String digits, List<String>ans, String temp){

    String letters = KEYS[digits.charAt(0)-'0'];
    for(int i =0;i<letters.length();i++){
        String newstring = temp+String.valueOf(letters.charAt(i));
        if(digits.length()>1)
            backtrack(digits.substring(1),ans,newstring);
        else
            ans.add(newstring);
    }
}

93. Restore IP Addresses (Medium)

In order to solve this problem, you need to know what is IP address. IP address is like XXX.XXX.XXX.XXX. Each XXX is larger or equal 0 and smaller or equal 255. Each IP address has four parts. The length of these four parts could be 1, 2 or 3. But if the length is not 1, 0 cannot be the first number in one part. Such as 00, 01, 012 are invalid. We use recursion and backtrack to solve this problem. In my algorithm, n means how many parts we already find. If n==4, this means we find a possible IP address. k is the length of each part. We try different length until we find a valid address. Remember we also need add ‘.’ to divide four parts.

Time complexity is O(n). Space complexity depends on the input. Here is the link.

public List<String> restoreIpAddresses(String s) {
    List<String> res = new ArrayList<String>();
    helper(s, 0, "", res);
    return res;
}
public void helper(String s, int n, String out, List<String> res) {
    if (n == 4) {
        if (s.isEmpty()) res.add(out);
        return;
    }
    for (int k = 1; k < 4; ++k) {
        if (s.length() < k) break;
        int val = Integer.parseInt(s.substring(0, k));
        if (val > 255 || k != String.valueOf(val).length()) continue;
        helper(s.substring(k), n + 1, out + s.substring(0, k) + (n == 3 ? "" : "."), res);
    }
}

79. Word Search (Medium)

We usually combine backtrack with dfs to solve problems. This problem is one of them. We use dfs to find the target string in the board. And if the string we find is not the target string, we backtrack to the previous step and continue to find the target string. If we find the target string, the algorithm should stop and return answer. I use a 2D boolean array as the visited array. Actually, we don’t need to use extra space. We can just change the value in board. For example, change it to ‘#'. After using dfs and backtracking, we restore its origin value.

Time complexity is O(mn). mn is the size of board. Space complexity is O(mn). Here is the link.

public boolean exist(char[][] board, String word) {
    int m = board.length;
    int n = board[0].length;
    if(m==0||n==0)return false;
    boolean [][]visited = new boolean[m][n];
    for(int i =0;i<m;i++){
        for(int j =0;j<n;j++){
            if(board[i][j]==word.charAt(0)){
                if(backtrack(board,word,i,j,visited))
                    return true;
            }
        }
    }
    return false;
}

public boolean backtrack(char[][] board, String word, int i, int j,boolean [][]visited){
    int m = board.length;
    int n = board[0].length;
    if(i<0||j<0||i>=m||j>=n||board[i][j]!=word.charAt(0)||visited[i][j])return false;
    if(word.length()==1)return true;
    visited[i][j]=true;
    int[][] directions = {{-1,0},{0,-1},{1,0},{0,1}};
    for(int[]direct:directions){
        int x = i + direct[0];
        int y = j + direct[1];
        if(backtrack(board,word.substring(1),x,y,visited))
            return true;
    }
    visited[i][j]=false;
    return false;
}

257. Binary Tree Paths (Easy)

A very easy problem. We just need to use dfs to find all possible paths.

Time complexity is O(n). Space complexity is O(n). n is the number of nodes in the tree. Here is the link.

public List<String> binaryTreePaths(TreeNode root) {
    List<String>ans = new ArrayList();
    if(root == null)return ans;
    dfs(root,ans,"");
    return ans;
}

public void dfs(TreeNode root, List<String>ans,String str){
    if(root == null)return;
    if(root.left==null && root.right == null){
        str+=String.valueOf(root.val);
        ans.add(str);
        return;
    }
    str+=String.valueOf(root.val)+"->";
    dfs(root.left,ans,str);
    dfs(root.right,ans,str);
}

46. Permutations (Medium)

We need to find all permutations, so we use dfs and backtrack to solve this problem. We also need a visited array to record if a value is already in our list.

Time complexity is O(n!). Space complexity is O(n!). If we have n numbers, the number of permutations is n!. Here is the link.

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>>ans = new ArrayList();
    if(nums.length==0)return ans;
    boolean[]visited = new boolean[nums.length];
    help(nums,ans,visited,new ArrayList());
    return ans;
}
public void help(int[] nums,List<List<Integer>>ans,boolean[]visited,List<Integer>list){
    if(list.size()==nums.length){
        ans.add(new ArrayList(list));
        return;
    }
    for(int i =0;i<nums.length;i++){
        if(visited[i])continue;
        visited[i]=true;
        list.add(nums[i]);
        help(nums,ans,visited,list);
        visited[i]=false;
        list.remove(list.size()-1);
    }
}

47. Permutations II (Medium)

This problem is exactly same as the last problem. But we need to delete duplicate permutations. We can use a hashset to store our answers. This will prevent storing same permutations. What’s more, we can sort the array. And check if next number is same as the current number. If they have same value, we may get the same result. We need to skip the same number in the same level.

Time complexity is O(n!). Space complexity: O(n + k). If we have n numbers, the number of permutations is n!. Here is the link.

public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>>ans = new ArrayList();
    if(nums.length==0)return ans;
    boolean[]visited = new boolean[nums.length];
    Arrays.sort(nums);
    help(nums,ans,visited,new ArrayList());
    return ans;
}
public void help(int[] nums,List<List<Integer>>ans,boolean[]visited,List<Integer>list){
    if(list.size()==nums.length){
        ans.add(new ArrayList(list));
        return;
    }
    for(int i =0;i<nums.length;i++){
        if(visited[i])continue;
        visited[i]=true;
        list.add(nums[i]);
        help(nums,ans,visited,list);
        visited[i]=false;
        list.remove(list.size()-1);
        while(i+1<nums.length && nums[i+1]==nums[i])i++;
    }
}

77. Combinations (Medium)

This problem is same as the last problem. But we can use some tricks to improve algorithm. At first, [2,3] and [3,2] are same. We only need one of them as the answer. So we want to make sure all our answers are ascending order. This is easy, we just need to pass the current value to next recursion and make sure next possible value is larger than current value. This can also help us to save space for visited array, because visited values are smaller and we will not iterate them again.

Time complexity: O(C(n, k)). Space complexity: O(k). Here is the link.

public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>>ans = new ArrayList();
    if(n==0)return ans;
    help(n,ans,0,new ArrayList(),k);
    return ans;
}

public void help(int n,List<List<Integer>>ans,int j,List<Integer>list,int k){
    if(list.size()==k){
        ans.add(new ArrayList(list));
        return;
    }
    for(int i =j+1;i<=n;i++){
        list.add(i);
        help(n,ans,i,list,k);
        list.remove(list.size()-1);
    }
}

39. Combination Sum (Medium)

In this problem, we can use one element unlimited number of times. The index we pass from current recursion to next is still current value’s index. Therefore, we can use same value unlimited number of times. If we find the value is larger than the target, we return to the previous recursion.

Here is the link.

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    Arrays.sort(candidates);
    List<List<Integer>>ans = new ArrayList();
    List<Integer>temp = new ArrayList();
    help(candidates,target,ans,temp,0);
    return ans;
}

private static void help(int[] candidates,int target,List<List<Integer>>ans,List<Integer>temp,int index){
    if(target == 0){
        ans.add(new ArrayList(temp));
        return;
    }
    for(int i = index;i<candidates.length;i++){
        if(candidates[i]>target)return;
        temp.add(candidates[i]);
        help(candidates,target-candidates[i],ans,temp,i);
        temp.remove(temp.size()-1);
    }
}

40. Combination Sum II (Medium)

This problem is same as the last problem. The only difference is we cannot use an element unlimited number of times. Therefore, we need to change the value of index that we pass to the next recursion. And we need to skip all same values in iteration.

Ref: (https://massivealgorithms.blogspot.com/2014/06/leetcode-combination-sum-darrens-blog.html)

(1) Let us see the difference between Combination Sum and Combination Sum II:

The input of Combination Sum has no dups, but each element can be used for MORE than one time.

The input of Combination Sum II has dups, but each element can be used for ONLY one time.

(2) Let us understand the time complexity of Combination Sum II at the beginning:

O(k * 2 ^ n) is the time complexity of Combination Sum II:

k is average length of each solution, and we need O(k) time to copy new linkedlist when we get one combination.

Solution space:

Since we use one element ONLY for one time, so, for the combinations with k elements, the number of different choices is C(n, k). And most of the time, this number is far smaller than k. But what is the worst case? int[] arr = {1,1,1,1,1,1,1,1,1}, target is 2, in this case, the number can actually reach C(n,k).

Considering that the combinations may have different length, which range from 0 ~ n. So, there are at most C(n,0) + C(n,1) + C(n,2) + … C(n,n) solutions. We know that C(n,0) + C(n,1) + C(n,2) + … C(n,n) = 2^n. Then we got the time complexity of Combination Sum II which is O(k * 2 ^ n).

(3) Then how we convert Combination Sum to Combination Sum II?

For example, given int[] arr = {2, 3, 4, 5, 6} and target is 10 and each element can be used for MORE than once.

Actually, it is same with the problem: given int[] arr = {2, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6, 6}, and target 10, each element can be used for ONLY one time, which is the same description of Combination Sum II.

And you must find that for the new array, each element E, which is smaller than target, will expand to ceil(target/E). Assume the new array has length n’, we can get the time complexity which is O(k * 2 ^ n’) using the same analysis of Combination Sum II.

Here is the link.

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    Arrays.sort(candidates);
    List<List<Integer>>ans = new ArrayList();
    List<Integer>temp = new ArrayList();
    help(candidates,target,ans,temp,-1);
    return ans;
}

    private static void help(int[] candidates,int target,List<List<Integer>>ans,List<Integer>temp,int index){
    if(target == 0){
        ans.add(new ArrayList(temp));
        return;
    }
    for(int i = index+1;i<candidates.length;i++){
        if(candidates[i]>target)return;
        temp.add(candidates[i]);
        help(candidates,target-candidates[i],ans,temp,i);
        temp.remove(temp.size()-1);
        while(i+1<candidates.length&&candidates[i+1]==candidates[i])i++;
    }
}

78. Subsets (Medium)

In this problem, we need to add current list to our answer in each recursion. We also need to add empty set at first.

Time complexity: O(N×2^N) to generate all subsets and then copy them into output list. Space complexity: O(N×2^N) to keep all the subsets of length N, since each of N elements could be present or absent. Here is the link.

public List<List<Integer>> subsets(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> ans = new ArrayList();
    ans.add(new ArrayList());
    if(nums.length==0)return ans;
    help(nums,ans,new ArrayList(),0);
    return ans;
}
public void help(int[]nums,List<List<Integer>> ans,List<Integer>list,int index){
    if(index==nums.length)return;
    for(int i =index;i<nums.length;i++){
        list.add(nums[i]);
        ans.add(new ArrayList(list));
        help(nums,ans,list,i+1);
        list.remove(list.size()-1);
    }
}

90. Subsets II (Medium)

This problem is similar to the last problem. But we need to skip duplicate values.

Time complexity: O(N×2^N) to generate all subsets and then copy them into output list. Space complexity: O(N×2^N) to keep all the subsets of length N, since each of N elements could be present or absent. Here is the link.

public List<List<Integer>> subsetsWithDup(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> ans = new ArrayList();
    ans.add(new ArrayList());
    if(nums.length==0)return ans;
    help(nums,ans,new ArrayList(),0);
    return ans;
}
    public void help(int[]nums,List<List<Integer>> ans,List<Integer>list,int index){
    if(index==nums.length)return;
    for(int i =index;i<nums.length;i++){
        list.add(nums[i]);
        ans.add(new ArrayList(list));
        help(nums,ans,list,i+1);
        list.remove(list.size()-1);
        while(i+1<nums.length && nums[i]==nums[i+1])i++;
    }
}

131. Palindrome Partitioning (Medium)

We find all subsets in last problem. In this problem, we need to find all substrings. The way to find substring is similar to the way find subsets. We also need a function to check if a substring is a palindrome string. We can use two pointers to check palindrome strings.

Time complexity: O(2^n). Space complexity: O(n). Here is the link.

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

public void help(List<List<String>>ans,List<String>list,int start,String s){
    if(start == s.length()){
        ans.add(new ArrayList(list));
        return;
    }
    for(int i =start;i<s.length();i++){
        String substring = s.substring(start,i+1);
        if(!palindrome(substring))continue;
        list.add(substring);
        help(ans,list,i+1,s);
        list.remove(list.size()-1);
    }
}

public boolean palindrome(String s){
    int left = 0;
    int right =s.length()-1;
    while(left<right){
        if(s.charAt(left)!=s.charAt(right))
            return false;
        left++;
        right--;
    }
    return true;
}

37. Sudoku Solver (Hard)

We fill in each empty cell with number 1 to 9 and check whether it is valid. If it is valid, we move to next recursion. When we back to the current recursion, we need to restore its origin value ‘.'. In order to check whether current value is valid, we check whether the same row, same column and same sub-box has the same value. When i==9, this means we fill in all empty cells successfully. When j ==9, this means we fill in empty cells in one row successfully and we need to move to next row.

Time Complexity - O(9m)， Space Complexity - O(m)， m is the number of ‘.'. Here is the link.

public void solveSudoku(char[][] board) {
    helper(board,0,0);
}
private static boolean helper(char[][]board,int i, int j){
    if(i==9)return true;
    if(j>=9)return helper(board,i+1,0);
    if(board[i][j]!='.')return helper(board,i,j+1);
    for(char c = '1';c<='9';c++){
        if(!isValid(board,i,j,c))continue;
        board[i][j]=c;
        if(helper(board,i,j+1))return true;
        board[i][j]='.';
    }
    return false;
}
private static boolean isValid(char[][]board,int i,int j,char val){
    for(int m =0;m<9;m++){
        if(board[i][m]==val)return false;
    }
    for(int n = 0;n<9;n++){
        if( board[n][j]==val)return false;
    }
    int x = i/3;
    int y = j/3;
    
    for(int m = x*3;m<x*3+3;m++){
        for(int n =y*3;n<y*3+3;n++){
            if(board[m][n]==val)
                return false;
        }
    }
    return true;
}

51. N-Queens (Hard)

In last problem, we try 9 numbers in an empty cell. While in this problem, we try n positions for each row. At first, we build a board. We can also instead build a string to represent the board. After initiating the board, we place the ‘Q’ at n positions for each row. If current position is valid, we move to next row. If it’s not valid, we move to next position. We need to find all possible solutions, so we need to restore its origin value after recursion. If we find i = board.length, this means we already place n queens in valid positions. We add it as the answer.

In order to prove a position is valid, we need to check the same column and two diagonal directions. We don’t need to check the same row, because if a position is valid, we jump to next row.

Time Complexity - O(n^n), Space Complexity - O(n). My solution’s space complexity is O(n^n), but we can improve it by using string. Here is the link.

public List<List<String>> solveNQueens(int n) {
    List<List<String>>ans = new ArrayList();
    char[][]board= new char[n][n];
    for(int i =0;i<n;i++){
        for(int j =0;j<n;j++)
            board[i][j]='.';
    }
    help(ans,board,0);
    return ans;
}
public void help(List<List<String>>ans,char[][]board,int i){
    if(i==board.length){
        List<String>res = new ArrayList();
        for(int m = 0;m<board.length;m++){
            String row = "";
            for(int n =0;n<board[m].length;n++){
                row+=String.valueOf(board[m][n]);
            }
            res.add(row);
        }
        ans.add(new ArrayList(res));
        return;
    }
    for(int m =0; m<board[0].length;m++){
        if(isvalid(board,i,m)){
            board[i][m]='Q';
            help(ans,board,i+1);
            board[i][m]='.';
        }
    }
}

public boolean isvalid(char[][]board,int i, int j){
    for(int n = i;n>=0;n--){
        if( board[n][j]=='Q')return false;
    }
    for(int m = i,n = j;m>=0 && n>=0;m--,n--){
        if(board[m][n]=='Q')
            return false;
    }
    for(int m = i,n = j;m>=0 && n<board[0].length;m--,n++){
        if(board[m][n]=='Q')
            return false;
    }
    return true;
}