A general approach to backtracking questions in Java (Subsets, Permutations, Combination Sum, Palindrome Partitioning)


  • 312
    I

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

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

    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);
        }
    }
    

    Subsets II (contains duplicates) : https://leetcode.com/problems/subsets-ii/

    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);
        }
    } 
    

    Permutations : https://leetcode.com/problems/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);
          }
       }
    } 
    

    Permutations II (contains duplicates) : https://leetcode.com/problems/permutations-ii/

    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);
            }
        }
    }
    

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

    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);
            }
        }
    }
    

    Combination Sum II (can't reuse same element) : https://leetcode.com/problems/combination-sum-ii/

    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); 
            }
        }
    } 
    

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

    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;
       return true;
    } 
    

  • 12
    B

    why in the first code snippet, the array needs to be sorted?


  • 1
    G

    No necessary. i guess it is to make it "general".


  • 56

    Backtracking can be solved always as follows:

    Pick a starting point.
    while(Problem is not solved)
        For each path from the starting point.
            check if selected path is safe, if yes select it
            and make recursive call to rest of the problem
            before which undo the current move.
        End For
    If none of the move works out, return false, NO SOLUTON.
    

  • 7
    Z

    Nice Summary !

    I think below part is difficult to reason about it's runetime peformance, the for loop make things complicated.

        for(int i = start; i < nums.length; i++){
            tempList.add(nums[i]);
            backtrack(list, tempList, nums, i + 1);
            tempList.remove(tempList.size() - 1);
        }
    

    Rather, this kind of code seems simpler for me:

        public List<List<Integer>> subsets(int[] ns) {
            List<List<Integer>> acc = new ArrayList<>();
            
            recur(acc, ns, new Stack<>(), 0);
            return acc;
        }
        
        private void recur(List<List<Integer>> acc, int [] ns, Stack path, int start){
            if(ns.length == start){
                acc.add(new ArrayList<>(path));
                return;
            }
                
            // take ns[start]
            path.push(ns[start]);
            recur(acc, ns, path, start + 1);
            path.pop();
            
            // dont take ns[start]
            recur(acc, ns, path, start + 1);
        }
    
    

  • 2
    L

    @bargitta

    You can see this link:https://web.archive.org/web/20160405044050/https://leetcode.com/problems/subsets/

    This problem had a note:Elements in a subset must be in non-descending order.

    But now this note is deleted. So you do not have to sort first.


  • 0
    W

    Your idea is really helpful. Thanks


  • 0
    A

    thanks a lot, I could not solve these kinds of problems at first :)


  • 1
    M

    @ZZJJ
    Your code is elegant and easy to understand.
    I have modified your code to solve the problem Subset II which contains deplicates. However, it works very slow. I was wondering if you could make it better. Here is the problem https://leetcode.com/problems/subsets-ii/ My modified code is as follows.

    public class Solution {
        public List<List<Integer>> subsetsWithDup(int[] nums) {
            List<List<Integer>> acc = new ArrayList<>();
            Arrays.sort(nums);
            HashSet<List<Integer>>a=new HashSet<>();
            recur(acc, nums, new Stack<>(), 0,a);
            return acc;
        }
        
        private void recur(List<List<Integer>> acc, int [] nums, Stack path, int start,HashSet<List<Integer>>a){
            if(nums.length == start){
                acc.add(new ArrayList<>(path));
                return; 
            }
                
                // take ns[start]
                
                path.push(nums[start]);
                ArrayList<Integer>x=new ArrayList<>(path);
                if(!a.contains(x))
                {
                    a.add(x);
                    recur(acc, nums, path, start + 1,a);
                }
                    path.pop();
    
                // dont take ns[start]
                recur(acc, nums, path, start + 1,a);
            
        }
    }
    

  • 4
    J

    for the subset problem, I wrote " list.add(tempList)“ instead of "list.add(new ArrayList<>(tempList))", and I got a list of empty lists as the result. Would someone tell me why this makes a difference?


  • 6
    J

    @jessebest Because when you add a list into the list<list>, it is passed as an object. The further operation changes the original object. Create a new list and clone the old one can solve this problem.


  • 4
    E

    It is really a great idea!!!
    But I find it is hard to analyse the complexity. Can any one give an explanation on the time and space complexity?


  • 0
    A

    This is a great approach and helps generalize similar set of problems. I have a question about optimization. I tried using this approach for the coin change problem (find number of coin combinations that equal amount) and it leads to TLE. Is there a way to add memoization to these kind of recursive solutions?


  • 0
    W

    @Jiminwen But why don't we also make a copy of the list when doing the recursion? (list as the parameter)


  • 0
    W

    @issac3 I understand "list.add(new ArrayList<>(tempList));" because of the reference thing.

    But why we don't need to make a copy when passing the list as a parameter in "backtrack(list, tempList, nums, i + 1);"


  • 1

    @whitecatgsd
    "But why don't we also make a copy of the list when doing the recursion? (list as the parameter)"

    It's have to be clone. Since in every recursion, we are using the same varibale named "list", if we don't clone it. the list you have if th final result list, which is a empty list(since we have a remove clause). Rather than a bunch of different lists.

    Let's make a inappropriate real life example:
    We hack Jimmy's credit card, then make 9 copies.
    10 different people using 10 different cards to purchase different things (assume it's workable).
    All transaction are recorded, but only one balance is reflected. Our Jimmy have to paid it even though he purchase nothing.

    In this case, 10 credits card is like the lists you take about. Eventually it's all list are same if you don't new List<int>(list).
    new List<int>(list) is like setting up a new account but already has something on it.(Like your family give you deposit, but afterward your account is independent from your family account).

    I hope this example helps.


  • 2
    X

    Any one can explain why "tempList.remove(tempList.size() - 1);" in Subsets?


  • 0
    X

    @Xueyuanshi said in A general approach to backtracking questions in Java (Subsets, Permutations, Combination Sum, Palindrome Partitioning):

    Any one can explain why "tempList.remove(tempList.size() - 1);" in Subsets?

    In fact. I cannot understand what happends after recurration. I can understand the result 1, 12, 123. But why 13 appears after 123? I think we remove the last element so it should be 12.


  • 0
    M

    @Xueyuanshi for 123, we remove the last two elements, and then put 3 to the tempList, so it should be 13. Just like depth-first search. sorry for poor English


  • 5

    @Xueyuanshi

    They keys are

            backtrack(list, tempList, nums, i + 1);
            tempList.remove(tempList.size() - 1);
    

    Execute next statement the "Remove last element". Then this level is completed, return back to the previous backtracking level.

    I attach the a simple graph of history of "list" in the whole call for input array "1,2,3", also some pointers for understanding. You might get a clue:

    empty -> 1 ->      1,2 -> 1,2,3 -> 1,2 -> 1 -> 1,3 ->   2,3 -> 1,2,3
         
             ^                                               ^
    1st level loop:i=0  ^                           ^   1st level: i = 1
                2nd  level loop: i = 1     2nd level loop: i = 2, 2nd ends
    			                     ......
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.