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


  • 212
    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;
    } 
    

  • 14
    H

    I don't think sorting the nums array is useful in your Combination Sum solution. Your for loop condition should also contain '&& nums[i] <= remain'


  • 2
    S

    great summarization!


  • 0
    H

    @hide why the loop condition has to contian the '&&num[i] <= remain' ? wasn't this condition considered at first?


  • 3
    H

    @HaitaoSun Say remain is 7, and you have numbers 8,9,10,11,12,13,14,15,16....... up to a huge number.

    If you put the condition in the for loop, it'll break out as soon as you see '8'. In OP's case, it'll check through all the numbers even when it could have just stopped after 8.

    So actually, sorting the numbers CAN be useful, if you add the condition I stated to the for loop. Otherwise, sorting the numbers is useless because you aren't using the fact that they're sorted to prune your possible results.


  • 0
    H

    @hide you are so right! Thanks man!


  • 2
    R

    To generate anagrams of a Given String using same structure

    List<String> anagrams (String input){
    	char[] inp = input.toCharArray();
    	List<String> result = new ArrayList();
       	backtrack(inp,result,inp.length,"");
       	return result;
    } 
    void backtrack(char[] input,List result,final int size,String str) {
    	if(str.length()==size){  // or can be input.length
    		result.add(new String(str));
    	}
    	else{
    		for(int i =0 ;i<input.length;i++){
    			if(str.contains(""+input[i])){
    				continue;
    			}
    			String newStr = str + input[i];
    			backtrack(input,result,size,newStr);
    		}
    	}
    }
    

  • 2
    S

    Nice post!
    But in permutation,

    if(tempList.contains(nums[i])) continue;
    

    is O(n) complexity, right?
    This makes the total complexity n^n instead of n! ?


  • 1
    N

    Hello . Fantastic summary ! I am trying to understand the reason behind !used[i - 1] for permutations II solution. Can you pls explain? Thank you.


  • 5
    L

    Hi, in the first one,list.add(new ArrayList<>(tempList));
    If I use list.add(templist); directly, then it's emptly. But if I print the elements, they are in the templist. Why this happens? Thanks.

    Got it. The templist will change later.


  • 0
    S

    @l78 I don't know either.Who can answer this question?


  • 0
    A

    @issac3 thanks so much for this!


  • 3
    H

    @smallskysky11 You need to create a COPY of templist before adding it. As you see templist keeps getting passed on as an argument and keeps getting modified. If you just add templist, all the modifications you make to templist get reflected in the final list.


  • 0
    This post is deleted!

  • 1
    R

    @nksharath I also have the same doubt, Can anyone please explain? Thanks !!


  • 0
    P

    What is the time complexity of combination sum?


  • 0
    R

    @poojasunder27 I think it`s, O(k * 2 ^ n), where k is the average length of all the combinations and n is the size of nums


  • 0
    Y

    @humachine Thanks you a lot!


  • 1
    L

    @nksharath you need '!used[i-1]' to differentiate whether we are processing the tempList which starts with 'i' or with 'i-1'.
    If we started with 'i-1' then used[i-1] is still true in that case even though 'nums[i] == nums[i-1]' we should not skip it.
    once we have finished processing 'i-1', used[i-1] is set to false and now processing 'i' doesn't make sense if nums[i]==nums[i-1] as it will generate the same results as 'i-1'


  • 0
    Y

    @issac3
    As for the problem Combination Sum, there is a typo in the Line 4: "new ArrayList<>( )" => "new ArrayList<Integer>( )".

    After correcting this typo, this solution still cannot pass the test.

    As for the test case [2, 2, 3], the output is [ [2, 2, 3], [2, 2, 3], [2, 2, 3] ], whereas the expected output is [ [2, 2, 3] ].

    The reason is that there is duplicate "2"s in the given test case, which needs to be dealt with in the "for"-loop.

    This is my solution to this problem.

    public class Solution {
        /**
         * @param candidates: A list of integers
         * @param target:An integer
         * @return: A list of lists of integers
         */
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            // write your code here
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            List<Integer> comb = new ArrayList<Integer>();
            Arrays.sort(candidates);
            helper(res, comb, target, 0, candidates);
            return res;
        }
        
        private void helper(List<List<Integer>> res, List<Integer> comb, int remSum, int pos, int[] candidates) {
            if (remSum == 0) {
                // MUST "new ArrayList<Integer>(comb)", otherwise res = [[]] (empty)
                res.add(new ArrayList<Integer>(comb));
                return;
            }
            // remSum = target - sum(comb) > 0
            for (int i = pos; i < candidates.length; i++) {
                // prune following search
                if (remSum - candidates[i] < 0) {
                    continue;
                }
                // avoid duplicates
                if (i != pos && candidates[i] == candidates[i - 1]) {
                    continue;
                }
                comb.add(candidates[i]);
                helper(res, comb, remSum - candidates[i], i, candidates);
                comb.remove(comb.size() - 1);
            }
        }
    }
    
    

Log in to reply
 

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