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


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

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

  • 4

    I'm really confused about this line:
    tempList.remove(tempList.size() - 1);


  • 0
    E

    Elegant and concise. Thank you.


  • 15
    E

    @Juan55555 To generate all possible permutations, we need to remove the least recently added element while we are going up the recursive call stack.
    In the first iteration of the for loop we add all permutations, that start with nums[0]. Then, before we can begin building all permutations starting with nums[1], we need to clear the tempList (which currently contains permutations from the first iteration of the for loop) - that's exactly what tempList.remove(tempList.size() - 1) line does.


  • 3
    C

    This answer is highly underrated..


  • 0
    Z

    a helpful and elgant answer. thx.


  • 0
    A

    awesome summary! love it!


  • 0
    D

    @issac3 This is great answer! Thanks a lot for combining all the approaches. I have doubt the purpose of below line in Permutation II problem. Can you confirm about its purpose please ? Thanks.

            if(used[i] || i > 0 && nums[i] == nums[i-1] && !used[i - 1]) continue;

  • 1
    D
    if(used[i] || i > 0 && nums[i] == nums[i-1] && !used[i - 1]) continue;
    
    

    in the above line, could you explain nums[i] == nums[i-1] && !used[i - 1] this ?

    Thanks.


  • 0
    T
    This post is deleted!

  • 2
    W

    @dreamer92 hi, think about this corner case.[1,1,1,1]
    we use [1a,1b,1c,1d] to mark the four 1s. with the

    if(used[i] || i > 0 && nums[i] == nums[i-1] && !used[i - 1]) continue;

    we make sure that 1a element is added to the result first, then 1b, then 1c, then 1d. In this case, we can only get 1 result. instead of getting 4!.


  • 1
    B

    @dreamer92 Hello, here is the meaning of the line you pointed out:
    You should notice that the array "nums" is sorted before we call the "backtrack" function, so this line simply means "if an element is already used in the permutation, we skip it OR if an element equals to the element before it, and the element before this element is not used in the permutation yet, we also skip it". In this way, we ensure the result is correct. Hope this answers your question :)


  • 1
    T

    The code in Permutation II:
    I was wondering if you made a mistake
    the condition should be i > 0 && nums[i] == nums[i - 1] && used[i - 1]
    not !used[i-1].
    because only if i-1 was used and i equals i-1,we can skip this.


  • 2
    O

    @toddler the purpose of checking if used[i-1] is to make sure the order of same value does not change, so of [1,1,2]. the second 1 cannot be used if the first has not been used yet, which means when(!used[i-1]) we skip the second 1.


  • 3
    F

    This approach can also be applied to the combinations problem
    https://leetcode.com/problems/combinations/

    public List<List<Integer>> combine(int n, int k) {
            List<List<Integer>> list=new ArrayList<List<Integer>>();
            backtrack(list,new ArrayList<Integer>(),n,k,1);
            return list;
        }
        public void backtrack(List<List<Integer>> list,ArrayList<Integer> templist,int n, int k,int start){
            if(templist.size()==k)
                list.add(new ArrayList<>(templist));
            else if(templist.size()>k)return;
                
            for(int i=start;i<=n;i++){
                templist.add(i);
                backtrack(list,templist,n,k,i+1);
                templist.remove(templist.size()-1);
            }
        }
    

  • 0
    V

    @bumblebeem @wondershow @Oliiiviiiaaa @issac3 I still am unsure of what the following line means? Could you please elaborate a little on it?

    if(used[i] || i > 0 && nums[i] == nums[i-1] && !used[i - 1]) continue;
    

    Also for subsets i, why are we sorting the arrays?

    What are the complexities of these algorithms? If we use sort, it is O(nlogn) otherwise O(n), is it?


  • 1
    U

    @vivekpatani I don't think there will be any O(n) or even O(nlogn) algorithm with this problem


  • 6
    C

    Isn't the following line has O(n) complexity?
    if(tempList.contains(nums[i])) continue;


  • 2
    D

    @csytracy Yes it is. The alternative would be to keep a boolean array to see which entries have already been used.

    private void permute(int[] nums, boolean[] seen, List<List<Integer>> result, Stack<Integer> current) {
        if (current.size() == nums.length) {
            result.add(new ArrayList<>(current));
        }
        
        for (int i = 0; i < nums.length; i++) {
            if (!seen[i]) {
                current.push(nums[i]);
                seen[i] = true;
                permute(nums, seen, result, current); 
                seen[i] = false;
                current.pop();
            }
        }
    }
    

    The problem with this is that we need O(n) extra space. This does not matter asymptotically since we already allocate that much space to track the current numbers. We could combine current and seen by using a map. But this would make the code a bit more ugly.


Log in to reply
 

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