12 popular LC Backtracking Problem Solution in one format

4368

1. Permutations

https://leetcode.com/problems/permutations/

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Java

Python

class Solution {
    List<List<Integer>> res;
    public List<List<Integer>> permute(int[] nums) {
        res = new ArrayList<>();
        if(nums.length == 0) return res;
        backtrack(nums, new ArrayList<>(), 0);
        return res;
    }
     void backtrack(int[] nums, List<Integer> temp, int n){
         if(n== nums.length){
             res.add(new ArrayList<>(temp));
             return;
         }
         for(int i = 0; i<nums.length; i++){
             if(temp.contains(nums[i])) continue;
             temp.add(nums[i]);
             backtrack(nums, temp, n+1);
             temp.remove(temp.size()-1);
         }
     }
}

2. Permutations II (contains duplicates) :

https://leetcode.com/problems/permutations-ii/

Input: nums = [1,1,2]
Output: [1,1,2], [1,2,1], [2,1,1]]

Java

Python

public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, new boolean[nums.length]);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, boolean [] used){
    if(tempList.size() == nums.length){
        list.add(new ArrayList<>(tempList));
    } else{
        for(int i = 0; i < nums.length; i++){
            if(used[i] || i > 0 && nums[i] == nums[i-1] && !used[i - 1]) continue;
            used[i] = true; 
            tempList.add(nums[i]);
            backtrack(list, tempList, nums, used);
            used[i] = false; 
            tempList.remove(tempList.size() - 1);
        }
    }
}

3. Letter Combinations of a Phone Number

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Java

Python

class Solution {
    List<String> res;
    String digits;
    String[] map;
    public List<String> letterCombinations(String digits) {
        this.res = new ArrayList<>();
        this.digits = digits;
        if(digits.length() == 0) return res;
        this.map = new String[]{
            "0",
            "1",
            "abc",
            "def",
            "ghi",
            "jkl",
            "mno",
            "pqrs",
            "tuv",
            "wxyz"
        };
        backtrack(new StringBuilder(),0);
        return res;
    }
    
    void backtrack(StringBuilder temp, int n){
        if(n==digits.length()){
            res.add(temp.toString());
            return;
        }
        String letters = map[digits.charAt(n) - '0'];
        for(int j = 0; j<letters.length(); j++){
            temp.append(letters.charAt(j));
            backtrack(temp,n+1);     // go to the next digit, not the letter
            temp.deleteCharAt(temp.length()-1);
        }
        
    }
}

4. Subsets

https://leetcode.com/problems/subsets/

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Java

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

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

Python

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        def bt(temp,n):
            nonlocal res
            res.append(temp[:])
            for i in range(n,len(nums)):
                temp.append(nums[i])
                bt(temp,i+1)
                temp.pop()
        bt([],0)
        return res

5. Subsets II (contains duplicates)

https://leetcode.com/problems/subsets-ii/

Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

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

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

6. Combination Sum

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

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]


public List<List<Integer>> combinationSum(int[] nums, int target) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, target, 0);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
    if(remain < 0) return;
    else if(remain == 0) list.add(new ArrayList<>(tempList));
    else{ 
        for(int i = start; i < nums.length; i++){
            tempList.add(nums[i]);
            backtrack(list, tempList, nums, remain - nums[i], i); // not i + 1 because we can reuse same elements
            tempList.remove(tempList.size() - 1);
        }
    }
}

7. Combination Sum II (can't reuse same element)

https://leetcode.com/problems/combination-sum-ii/

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: [[1,1,6],[1,2,5],[1,7],[2,6]]

public List<List<Integer>> combinationSum2(int[] nums, int target) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, target, 0);
    return list;
    
}

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

8. Palindrome Partitioning

https://leetcode.com/problems/palindrome-partitioning/

	Input: s = "aab"
	Output: [["a","a","b"],["aa","b"]]

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        backtrack(res, s, new ArrayList<>(), 0);
        return res;
    }
    void backtrack(List<List<String>> res, String s, List<String> temp, int n){
        if(n == s.length()){
            res.add(new ArrayList(temp));
            return;
        }
        for(int i = n; i<s.length(); i++){
            if(isPalindrome(s, n, i)){
                temp.add(s.substring(n, i+1));
                backtrack(res,s,temp,i+1);
                temp.remove(temp.size()-1);
            }
        }
    }
    boolean isPalindrome(String s, int l, int r){
        while(l<r){
            if(s.charAt(l)!=s.charAt(r)) return false;
            l++;
            r--;
        }
        return true;
    }
}

9. Restore IP Address

https://leetcode.com/problems/restore-ip-addresses/

Example- 123245234 
   1.2.3.245234
   1.2.32.45234
   1.2.324.5234
   1.23.2.45234
   1.23.24.5234
   1.23.245.234 <- valid		1.23.245.234
   1.232.45.234 <- valid		1.232.45.234 
   1.232.452.34
   12.3.2.45234
   12.3.24.5234
   12.3.245.234 <-valid		12.3.245.234
   12.32.4.5234
   12.32.45.234 <-valid		12.32.45.234
   12.32.452.34
   12.324.5.234
   123.2.4.5234
   123.2.45.234 <- valid		123.2.45.234
   123.2.452.34
   123.24.5.234 <- valid		123.24.5.234
   123.24.52.34 <- valid		123.24.52.34
   123.24.523.4 
   123.245.2.34 <-valid		123.245.2.34
   123.245.23.4 <- valid		123.245.23.4

public List<String> restoreIpAddresses(String s) {
	List<String> res  = new ArrayList<>();
	backtrack(res, s, new StringBuilder(), 0, 0);
	return res;
}
void backtrack(List<String> res, String s, StringBuilder temp, int n, int count){
	if(n == s.length() && count == 4){

		res.add(temp.toString());
	}
	else if(count == 4) return;

	for(int i = n; i<s.length(); i++){
		String curr = s.substring(n, i+1);
		int num = Integer.valueOf(curr);
		if(curr.length()>1 && curr.charAt(0) == '0') return;
		if(num>255) return;
		StringBuilder sb = new StringBuilder(temp);
		temp.append(curr);
		if(count<3)temp.append(".");
		backtrack(res,s, temp, i+1, count+1);
		temp = sb;
	}
}

10. Generate Parentheses

https://leetcode.com/problems/generate-parentheses/

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        if(n== 0) return res;
        return backtrack(n, res, 0,0, "");
    }
    List<String> backtrack(int n, List<String> res, int open, int close, String s){
        if(s.length() == 2*n){
            res.add(s);
            return res;
        }
        if(open<n) res = backtrack(n, res, open+1, close, s+"(");
        if(close<open) res = backtrack(n, res, open, close+1, s+")");
        return res;
    }
}

11. Path Sum II

https://leetcode.com/problems/path-sum-ii/

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22

class Solution {
    List<List<Integer>> res;
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        res = new ArrayList<>();
        helper(root, targetSum, new ArrayList<>());
        return res;
    }
    void helper(TreeNode root, int targetSum, List<Integer> temp){
        if(root == null) return;
        targetSum-=root.val;
        temp.add(root.val);
        if(targetSum == 0 && root.left == null && root.right == null){
            res.add(new ArrayList<>(temp));
            temp.remove(temp.size()-1);
            return;
        }
        helper(root.left, targetSum, temp);
        helper(root.right, targetSum, temp);
        temp.remove(temp.size()-1);
    }
}

12. Word Search

https://leetcode.com/problems/word-search/

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

class Solution {
    int m,n;
    String word;
    char[][] board;
    public boolean exist(char[][] board, String word) {
        this.board = board;
        this.word = word;
        m = board.length;
        n = board[0].length;
        
        for(int i = 0; i<m; i++){
            for(int j = 0; j<n; j++){
                if(board[i][j] == word.charAt(0)){
                    if(backtrack(i,j, 0)) return true;
                }
            }
        }
        return false;
    }
    boolean backtrack(int i, int j, int idx){
        if(idx == word.length()) return true;
        char c = word.charAt(idx);
        if(i<0 || i>=m ||j<0 ||j>=n || board[i][j]!= c) return false;
        board[i][j] = '!';
        boolean found = backtrack(i+1, j, idx+1) || backtrack(i-1, j, idx+1) 
            || backtrack(i, j+1, idx+1)|| backtrack(i, j-1, idx+1);
        
        board[i][j] = c;
        return found;
    }
}

Thank you https://leetcode.com/issac3 for the format. Please vote if you find it helpful :)

Comments (2)