✅ All Backtracking Interview Problems - One Stop Destination
Nitin Kumar
1811
CareerDepth-First SearchHash Table

Let's start...

1. Subset - I [an integer array nums of unique elements, return all possible subsets (the power set)]
Problem link : https://leetcode.com/problems/subsets/

Approach - 1 : Backtracking [ C++ Code ]
Recursive Tree

Time Complexity : O(2^n) for generating every subset and O(k) to insert every subset in another data structure if the average length of every subset is k. Overall O(k * 2^n).
Space Complexity : O(2^n * k) to store every subset of average length k. Auxiliary space is O(n) if n is the depth of the recursion tree.

class Solution {
public:
    
    void solve(vector<int>&nums, vector<int>&path, vector<vector<int>>&paths, int start)
    {
        paths.push_back(path);
        
        for(int i=start;i<nums.size();i++){
            
            path.push_back(nums[i]);
            solve(nums,path,paths,i+1);
            path.pop_back();
        }
    }
    
    vector<vector<int>> subsets(vector<int>& nums) {
        
        vector<vector<int>>paths;
        vector<int>path;
        solve(nums,path,paths,0);
        return paths;
    }
};
Approach - 2 : Bit Manipulation [ C++ Code ]

Time Complexity : O(2^n) for generating every subset and O(n) to iterate over the nums. Overall O(n * 2^n).
Space Complexity : O(2^n * k) to store every subset of average length k.

class Solution {
public:
    
    vector<int> FindSubSet(int no,vector<int>&nums)
    {
        vector<int>re;
        int i = 0;
        while(no)
        {
            if(no&1)
            {
                re.push_back(nums[i]);
            }
            i++;
            no>>=1;
        }
        return re;
    }
    
    vector<vector<int>> subsets(vector<int>& nums) 
    {
        int n = nums.size();
        vector<vector<int>>ans;
        int total = 1<<n; // total = 2^n subsets
        
        for(int i=0;i<total;i++)
        {
            vector<int>temp = FindSubSet(i,nums);
            ans.push_back(temp);
        }
        return ans;
    }
};
Approach - 3 : Pick & Not Pick - 1 [ C++ Code ]
Recursive Tree

Time Complexity : O(2^n) for generating every subset and O(k) to insert every subset in another data structure if the average length of every subset is k. Overall O(k * 2^n).
Space Complexity : O(2^n * k) to store every subset of average length k. Auxiliary space is O(n) if n is the depth of the recursion tree.

class Solution {
public:
    
    void solve(vector<int> &nums, int i, vector<vector<int>>&ans, vector<int>&sub)
    {
        if(i==nums.size())
        {
            ans.push_back(sub);
            return;
        }
        
        
        // pick 
        sub.push_back(nums[i]);
        solve(nums, i+1, ans, sub);
        sub.pop_back();
        
        // don't pick
        solve(nums, i+1, ans, sub);
        
    }
    
    vector<vector<int>> subsets(vector<int>& nums) {
        
        vector<vector<int>> ans;
        vector<int>sub;       
        solve(nums, 0, ans, sub); 
        return ans;
    }
};
Approach - 4 : Pick & Not Pick - 2 [ C++ Code ]

Time Complexity : O(2^n) for generating every subset and O(k) to insert every subset in another data structure if the average length of every subset is k. Overall O(k * 2^n).
Space Complexity : O(2^n * k) to store every subset of average length k. Auxiliary space is O(n) if n is the depth of the recursion tree.

class Solution {
public:
    
    void solve(vector<int> &nums, int i, vector<vector<int>>&ans, vector<int>sub)
    {
        if(i==nums.size())
        {
            ans.push_back(sub);
            return;
        }
        
        solve(nums, i+1, ans, sub);
        sub.push_back(nums[i]);
        solve(nums, i+1, ans, sub);
    }
    
    vector<vector<int>> subsets(vector<int>& nums) {
        
        vector<vector<int>>ans;
        vector<int>sub;       
        solve(nums, 0, ans, sub); 
        return ans;
    }
};

2. Subset - II [an integer array nums that may contain duplicates, return all possible subsets (the power set).]
Problem link : https://leetcode.com/problems/subsets-ii/

Approach - 1 : Brute Force (Backtracking) [ C++ Code ]

Time Complexity : O(2^n*( klog(x) )).2^n, 2^n for generating every subset and k*log(x) to insert every combination of average length k in a set of size x. After this, we have to convert the set of combinations back into a list of list /vector of vectors which takes more time.
Space Complexity : O(2^n * k) to store every subset of average length k. Since we are initially using a set to store the answer another O(2^n * k) is also used.

class Solution{
public:
    
    void solve(vector<int>&nums, int i, vector<int>ds, set<vector<int>>&st) 
    {
        if(i == nums.size()) 
        {
            sort(ds.begin(), ds.end());
            st.insert(ds);
            return;
        }
        
        ds.push_back(nums[i]);
        solve(nums, i + 1, ds, st);
        ds.pop_back();
        solve(nums, i + 1, ds, st);
    }
    
    vector<vector<int>>subsetsWithDup(vector<int>& nums) 
    {
        vector<vector<int>>ans;
        set<vector<int>>st;
        vector<int>ds;
        
        solve(nums, 0, ds, st);
        for(auto &v : st) 
            ans.push_back(v);
        return ans;
    }
};
Approach - 2 : Optimized (Backtracking) [ C++ Code ]

Time Complexity : O(2^n) for generating every subset and O(k) to insert every subset in another data structure if the average length of every subset is k. Overall O(k * 2^n).
Space Complexity : O(2^n * k) to store every subset of average length k. Auxiliary space is O(n) if n is the depth of the recursion tree.

class Solution {
public:
    
    void solve(int ind, vector<int>&nums, vector<int>&path, vector<vector<int>>&paths)
    {
        paths.push_back(path);
        
        for(int i=ind;i<nums.size();i++)
        {    
            if(i!=ind and nums[i] == nums[i-1]) continue; // To avoid duplicate subsets
            
            path.push_back(nums[i]);
            solve(i+1, nums, path, paths);
            path.pop_back();
        }
    }
    
    vector<vector<int>> subsetsWithDup(vector<int>& nums) 
    {    
        vector<vector<int>>paths;
        vector<int>path;
        sort(nums.begin(), nums.end()); // sorting is most important --- so that order of duplicate subsets is same
        solve(0, nums, path, paths);    // [1,4,4] == [4,1,4] , both are same so no need to include both in answer
        return paths; 
    }
};

3. Permutation - I [an array nums of distinct integers, return all the possible permutations]
Problem link : https://leetcode.com/problems/permutations/

Approach : Recursion & Backtracking [ C++ Code ]

Time Complexity : O(N! * N), N! for generating all permutations and another N for inserting each permutaion instance into answer.
Space Complexity : N size for storing each permutation instance, so overall O(N * N!).

class Solution {
public:
   
	void permuteRecursive(vector<int> &num, int index, vector<vector<int>>&ans) 
    {
		if (index == num.size()) {
		    // one permutation instance
		    ans.push_back(num);
		    return;
		}
		
		for (int i = index; i < num.size(); i++) 
        {
		    swap(num[index], num[i]);
		    permuteRecursive(num, index + 1, ans);
		    swap(num[index], num[i]); // backtrack
		}
    }
    
    vector<vector<int>> permute(vector<int> &num) {
        
	    vector<vector<int>>ans;
	    permuteRecursive(num, 0, ans);
	    return ans;
    }
};

4. Permutation - II [an array nums that might contain duplicates, return all possible unique permutations]
Problem link : https://leetcode.com/problems/permutations-ii/

Approach - 1 : Using Permutation - I [ C++ Code ]

Time Complexity : O(n! * n! * logn!) it is worst case when all elements are unique.
Space Complexity : O(n! * n)

class Solution {
public:

    void solve(vector<int> &nums, int index,  set<vector<int>> &s) {
        if(index == nums.size()) {
            s.insert(nums); // generate all permutations and store it into set
            return;
        }
        
        for(int i = index; i < nums.size(); i++) {
            swap(nums[index], nums[i]);
            solve(nums, index + 1, s);
            swap(nums[index], nums[i]);
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> ans;
        set<vector<int>>s;
        solve(nums, 0, s);
        
        for(auto &i: s)
            ans.push_back(i);
        return ans;
    }
};
Approach - 2 : Recursive (Optimized & Pass by value) [ C++ Code ]

Time Complexity : O(nlogn) + O(n! * n) ~ O(n! * n)
Space Complexity : O(n! * n)

class Solution {
public:
    
    // main swapping takes place
    void permute(vector<int>nums, int index, vector<vector<int>>& ans) {
        
        if (index == nums.size()) {
            ans.push_back(nums);
            return;
        } 
       
        for (int i = index; i < nums.size(); i++) {
            
            if(i != index && nums[index] == nums[i]) continue;
            swap(nums[index], nums[i]);
            permute(nums, index + 1, ans);
        }   
    }
    
    vector<vector<int>> permuteUnique(vector<int>& nums) {
    
        sort(nums.begin(), nums.end());
        vector<vector<int>>ans;
        permute(nums, 0, ans);
        return ans;
    }
};
Approach - 3 : Recursive (Optimized & Pass by reference) [ C++ Code ]

Time Complexity : O(nlogn) + O(n! * n) ~ O(n! * n)
Space Complexity : O(n! * n)

class Solution {
public:
    
    // main swapping takes place
    void permute(vector<int>&nums, int index, vector<vector<int>>& ans) {
        
        if (index == nums.size()) {
            ans.push_back(nums);
            return;
        } 
       
        for (int i = index; i < nums.size(); i++) {
            
            if(i != index && nums[index] == nums[i]) continue;
            swap(nums[index], nums[i]);
            permute(nums, index + 1, ans);
			swap(nums[index], nums[i]);
        }   
    }
    
    vector<vector<int>> permuteUnique(vector<int>& nums) {
    
        sort(nums.begin(), nums.end());
        vector<vector<int>>ans;
        permute(nums, 0, ans);
        return ans;
    }
};
Approach - 4 : Iterative (using in built next_permutation function) [ C++ Code ]

Time Complexity : O(nlogn) + O(n! * n), The nextPermutation() function takes O(N) time to find the next permutation and there are N! number of permutations for an array of size N. O(nlogn) takes to sort nums array.
Space Complexity : O(1) No auxiliary space is used.

class Solution {
public:
    // next_permutation : it will return false when arrangement is not greater than the previous, 
    // but the lowest possible (sorted in ascending order)
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>>ans;
        sort(nums.begin(), nums.end()); 
        do {
            ans.push_back(nums);
        } while(next_permutation(nums.begin(), nums.end()));  
        return ans;
    }
};
Approach - 5 : Iterative (next_permutation) [ C++ Code ]

Time Complexity : O(nlogn) + O(n! * n). The nextPermutation() function takes O(N) time to find the next permutation and there are N! number of permutations for an array of size N. O(nlogn) takes to sort nums array.
Space Complexity : O(1) No auxiliary space is used.

class Solution {
public:
    
    void reverse(vector<int>& nums, int i, int j) {
        while (i < j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            i++;
            j--;
        }
    }

    void swap(vector<int>& nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    // find next permutation - [2, 1, 5, 4, 3, 0, 0], breakpoint index = 1, from last till breakpoint we have observed 
    // there is an increasing order.
    bool nextPermutation(vector<int>& nums) {
        // can use existing function
        // next_permutation(nums.begin(), nums.end());

        int n = nums.size();
        // initialize variable:
        int breakPoint = -1;

        // find a breakpoint:
        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                breakPoint = i;
                break;
            }
        }

        // if no breakpoint is found, then reverse entire array and return as it is
        // reverse the whole array - for smallest permutation because we are already on the largest permutation
        if (breakPoint == -1) {
            // reverse(nums.begin(), nums.end());
            reverse(nums, 0, n-1); 
            return false;
        }

        // if found a breakpoint, then again iterate from the end and find
        // largest element which is greater than breakpoint element , and then
        // swap both and reverse from 'breakpoint+1' to 'end'
        for (int i = n - 1; i > breakPoint; i--) {
            if (nums[i] > nums[breakPoint]) {
                // swap(nums[breakPoint], nums[i]);
                swap(nums, breakPoint, i);
                break;
            }
        }
        // reverse(nums.begin() + breakPoint + 1, nums.end());
        reverse(nums, breakPoint+1, n-1);
        return true;
    }
    
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        do 
        {
            ans.push_back(nums); // push all permutations & stop when original array comes again
            
        } while(nextPermutation(nums));
        return ans;
    }
};

5. Combination Sum - I
Problem link : https://leetcode.com/problems/combination-sum/

CASE 1 : Note : There must be always +ve number in input array

Approach - 1 : Recursion & Backtracking (Bottom - Up [building sum up to target]) [ C++ Code ]

Time Complexity : O(2^t * k) where t is the target, k is the average length.
Space Complexity : O(k * x), k is the average length and x is the no. of combinations.

Reason: Assume if you were not allowed to pick a single element multiple times, every element will have a couple of options: pick or not pick which is 2^n different recursion calls, also assuming that the average length of every combination generated is k. (to put length k data structure into another data structure)

Why not (2^n) but (2^t) (where n is the size of an array)?

Assume that there is 1 and the target you want to reach is 10 so 10 times you can “pick or not pick” an element.

class Solution {
public:
    
    void solve(vector<int>&nums, int index, int curSum, int target, vector<vector<int>>&ans, vector<int>&temp)
    {
        if(curSum > target) return; 
        if(curSum == target){
            ans.push_back(temp); 
            return; // should return because we have +ve numbers only, so our target will increase after this.
        }

        for(int i=index;i<nums.size();i++) 
        {
            temp.push_back(nums[i]); 
            // curSum += nums[i];
            solve(nums, i, curSum + nums[i], target, ans, temp); // you can choose same number multiple times
            // curSum -= nums[i];          
            temp.pop_back();
        }
    }
    
    vector<vector<int>> combinationSum(vector<int>& nums, int target) {
        
        vector<vector<int>>ans;
        vector<int>temp;
        int curSum = 0;
        solve(nums, 0, curSum, target, ans, temp);
        return ans;
    }
};
Approach - 2 : Recursion & Backtracking (Top - Down [reducing target to 0] - 1) [ C++ Code ]

Time Complexity : O(2^t * k) where t is the target, k is the average length.
Space Complexity : O(k * x), k is the average length and x is the no. of combinations.

class Solution {
public:
    
    void solve(vector<int>& nums, int i, int target, vector<vector<int>>&ans, vector<int>& temp)
    {
        if(target == 0) {
            ans.push_back(temp); 
            return; 
        }
        
        if(target < 0) return;
        
        if(i == nums.size()) return;
        
        // don't pick
        solve(nums, i+1, target, ans, temp);
        
        // pick
        temp.push_back(nums[i]); 
        solve(nums, i, target-nums[i], ans, temp); 
        temp.pop_back(); // backtrack
    }
    
    vector<vector<int>> combinationSum(vector<int>& nums, int target) {
        
        vector<vector<int>> ans; 
        vector<int> temp;    // temporary vector that tries all possible combination
        
        solve(nums, 0, target, ans, temp); 
        return ans; 
    }
};
Approach - 2 : Recursion & Backtracking (Top - Down [reducing target to 0] - 2) [ C++ Code ]

Time Complexity : O(2^t * k) where t is the target, k is the average length.
Space Complexity : O(k * x), k is the average length and x is the no. of combinations.

class Solution {
public:
    
    void solve(vector<int>&nums, int index, int target, vector<vector<int>>&ans, vector<int>&temp) {
        if(target == 0) {
            ans.push_back(temp); 
            return;
        }
        if(index == nums.size()) return;
        
        // pick 
        if(nums[index] <= target) {
            temp.push_back(nums[index]);
            solve(nums, index, target-nums[index], ans, temp); // you can choose same number multiple times     
            temp.pop_back();
        }
        // don't pick
        solve(nums, index+1, target, ans, temp);
    }
    
    vector<vector<int>> combinationSum(vector<int>& nums, int target) {
        
        vector<vector<int>> ans; 
        vector<int> temp;    // temporary vector that tries all possible combination
        
        solve(nums, 0, target, ans, temp); 
        return ans; 
    }
};

CASE 2 : Note : When there is +ve and -ve both type of numbers are present in input array.

Approach - 1 : Generate all subsets and take sum [ C++ Code ]

Time Complexity : O(2^n * n), 2^n for generating all the subsets, and O(n) for calculating the sum of each subset.
Space Complexity : O(2^n * n), 2^n recursive call so it will take 2^n auxiliary stack space, and another O(n) for storing the each subset into answer vector.

int sum(vector<int>&arr){
    
    int s=0;
    for(auto &x: arr)
        s += x;
    return s;
}

void solve(const vector<int>&arr, int index, vector<int>&sub, vector<vector<int>>&ans, int target)
{
    if(index == arr.size()){
        if(sum(sub)==target)
            ans.push_back(sub);
        return;
    }
    
    // pick
    sub.push_back(arr[index]);
    solve(arr, index+1, sub, ans, target);
    sub.pop_back();
    
    // don't pick
    solve(arr, index+1, sub, ans, target);
}

vector<vector<int>> findSubsetsThatSumToK(vector<int> arr, int n, int target)
{
    vector<vector<int>>ans;
    vector<int>sub;
    solve(arr, 0, sub, ans, target);
    return ans;
}
Approach - 2 : Recursion & Backtracking (1) [ C++ Code ]

Time Complexity : O(2^n), 2^n for generating all the subsets.
Space Complexity : O(2^n), 2^n recursive call so it will take 2^n auxiliary stack space.

#include <bits/stdc++.h>
using namespace std;

void solve(const vector<int>&arr, int index, vector<int>&sub, vector<vector<int>>&ans, int target, int sum)
{
    if(index == arr.size()) {
	    // got the new subset, total  - 2^n subsets
        if(sum==target && sub.size() > 0){ // don't take empty subset
            ans.push_back(sub);
        }
        return;
    }   
    
    // pick
    sub.push_back(arr[index]);
    sum += arr[index];
    solve(arr, index+1, sub, ans, target, sum);
    sum -= arr[index];    
    sub.pop_back();
    
    // don't pick
    solve(arr, index+1, sub, ans, target, sum);
}

vector<vector<int>> findSubsetsThatSumToK(vector<int> arr, int target)
{
    vector<vector<int>>ans;
    vector<int>sub;
    solve(arr, 0, sub, ans, target, 0);
    return ans;
}

int main() {
 
  vector < int > v {2,3,-3,0};
  int target = 0;

  vector < vector < int >> ans = findSubsetsThatSumToK(v, target);
  cout<<"no. of subsets : "<<ans.size()<<endl;
  cout << "Combinations are: " << endl;
  for (int i = 0; i < ans.size(); i++) {
    for (int j = 0; j < ans[i].size(); j++)
      cout << ans[i][j] << " ";
    cout << endl;
  }
}

Output

no. of subsets : 3
Combinations are:
3 -3 0
3 -3
0

Approach - 2 : Recursion & Backtracking (2) [ C++ Code ]

Time Complexity : O(2^n), 2^n for generating all the subsets.
Space Complexity : O(2^n), 2^n recursive call so it will take 2^n auxiliary stack space.

#include <bits/stdc++.h>
using namespace std;

void solve(const vector<int>&arr, int index, vector<int>&sub, vector<vector<int>>&ans, int target, int sum)
{   
    if(index == arr.size()) {
        // got the new subset, total  - 2^n subsets
        if(sum==target){ 
            ans.push_back(sub);
        }   
        return;
    }
    
    // pick
    sub.push_back(arr[index]);
    solve(arr, index+1, sub, ans, target, sum + arr[index]);
    sub.pop_back();
    
    // don't pick
    solve(arr, index+1, sub, ans, target, sum);
}

vector<vector<int>> findSubsetsThatSumToK(vector<int> arr, int target)
{
    vector<vector<int>>ans;
    vector<int>sub;
    solve(arr, 0, sub, ans, target, 0);
    return ans;
}


int main() {
 
  vector < int > v {2,3,-3,0};
  int target = 0;

  vector < vector < int >> ans = findSubsetsThatSumToK(v, target);
  cout<<"no. of subsets : "<<ans.size()<<endl;
  cout << "Combinations are: " << endl;
  for (int i = 0; i < ans.size(); i++) {
    for (int j = 0; j < ans[i].size(); j++)
      cout << ans[i][j] << " ";
    cout << endl;
  }
}

Output

no. of subsets : 4
Combinations are:
3 -3 0
3 -3
0

6. Combination Sum - II
Problem link : https://leetcode.com/problems/combination-sum-ii/

Approach - 1 : Recursion & Backtracking (Bottom - Up) [ C++ Code ]

Time Complexity : O(2^n * k), Assume if all the elements in the array are unique then the no. of subset you will get will be O(2^n). we also add the subset to our ans when we reach the base case that it will take average k.
Space Complexity : O(k * x), if we have x combinations then space will be x* k where k is the average length of the combination.

class Solution {
public:
    
    void solve(vector<int>& nums, int index, int sum, int target, vector<vector<int>>&ans, vector<int>&temp)
    {        
        if(sum == target){
            ans.push_back(temp);
            return;
        }
        if(index == nums.size()) return;
        
        for(int i=index;i<nums.size();i++)
        {
            if(i > index && nums[i] == nums[i-1]) continue; // to avoid duplicates
            if(sum + nums[i] > target) break; // important

            temp.push_back(nums[i]);
            // sum += nums[i];
            solve(nums, i+1, sum + nums[i], target, ans, temp);
            // sum -= nums[i];
            temp.pop_back();
        }
    }
    
    vector<vector<int>> combinationSum2(vector<int>& nums, int target) {
        
        vector<vector<int>>ans;
        vector<int>temp;
        int sum = 0;
        sort(nums.begin(), nums.end()); 

        solve(nums, 0, sum, target, ans, temp);
        return ans;
    }
};
Approach - 2 : Recursion & Backtracking (Top - Down) [ C++ Code ]

Time Complexity : O(2^n * k), Assume if all the elements in the array are unique then the no. of subset you will get will be O(2^n). we also add the subset to our ans when we reach the base case that it will take average k.
Space Complexity : O(k * x), if we have x combinations then space will be x * k where k is the average length of the combination.

class Solution {
public:
    
    void solve(vector<int>&nums, int index, int target, vector<vector<int>>&ans, vector<int>&temp) 
    {
          if (target == 0) {
            ans.push_back(temp);
            return;
          }
          if(index == nums.size()) return;
        
          for (int i = index; i < nums.size(); i++) 
          {
            if (i > index && nums[i] == nums[i - 1]) continue;
            if (nums[i] > target) break; // as numbers are already sorted, it means upcoming numbers are also greater than target, so break from here 
              
            temp.push_back(nums[i]);
            solve(nums, i + 1, target - nums[i], ans, temp);
            temp.pop_back();
          }
    }
    
    vector<vector<int>>combinationSum2(vector<int>&nums, int target) 
    {
        sort(nums.begin(), nums.end()); // doing this so that we can easily avoid duplicates
        vector<vector<int>>ans;
        vector<int>temp;
        
        solve(nums, 0, target, ans, temp);
        return ans;
    }
};

7. Combination Sum - III
Problem link : https://leetcode.com/problems/combination-sum-iii/

Approach : Recursion & Backtracking [ C++ Code ]

Time Complexity : O(2^9 * k), 2^9 for generating subsets, and each subset is made up of using k different numbers, so k will take for inserting into our answer.
Space Complexity : O(2^9 * k).

class Solution {
public:
    
    void solve(vector<int>&nums, int index, int k, int target, vector<vector<int>> &ans, vector<int> &temp)
    {
        if(k == 0)
        {
            if(target == 0) 
                ans.push_back(temp);
            return;
        }
        
        for(int i=index;i<nums.size();i++)    
        {
            if(nums[i] > target) break;
            temp.push_back(nums[i]);
            solve(nums, i+1, k-1, target-nums[i], ans, temp);
            temp.pop_back();
        }
    }
    
    vector<vector<int>> combinationSum3(int k, int n) 
    {
        vector<int>nums = {1,2,3,4,5,6,7,8,9};
        vector<vector<int>> ans;
        vector<int>temp;
        int target = n;

        solve(nums, 0, k, target, ans, temp);
        return ans;
    }
};

8. Combination Sum - IV
Problem link : https://leetcode.com/problems/combination-sum-iv/

Approach : Dynamic Programming [ C++ Code ]

Note : considers order important, permutations like (1, 1, 2), (1, 2, 1), and (2, 1, 1) are treated as different. Hence, the output is 7 unique ordered combinations instead of 4 unique combinations. That's why we have started from 0 again instead of index for take recursive call.

Time Complexity : O(n*target)
Space Complexity : O(n*target)

class Solution {
public:

    int solve(vector<int>&nums, int index, int target, vector<vector<int>>&dp) {
        if(target == 0) {
            return 1;
        }
        if(index == nums.size()) return 0;

        if(dp[index][target] != -1) return dp[index][target];
        
        // pick 
        int ans = 0;
        if(nums[index] <= target) {
            ans += solve(nums, 0, target-nums[index], dp); // you can start from 0 index again   
        }
        // don't pick
        ans += solve(nums, index+1, target, dp);
        return dp[index][target] = ans;
    }
    
    int combinationSum4(vector<int>& nums, int target) {

        int n = nums.size();
        vector<vector<int>>dp(n+1, vector<int>(target+1, -1));
        return solve(nums, 0, target, dp); 
    }
};

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

Approach - 1 : Recursion & Backtracking (Efficient & Intuitive) [ C++ Code ]

Time Complexity : O(2^n * n), For each of the O(2^n) partitions, checking whether each substring is a palindrome takes O(n) time.
Space Complexity : O(2^n * n), space required to store all the partitions, which gives us O(2^n * n) in worst case, e.g s = "aaaa".

class Solution {
public:
    
    bool isPalindrome(string& s, int i, int j) 
    {
        while(i <= j) {
            if(s[i++] != s[j--])
                return false;
        }
        return true;
    }
    
    // Draw recursive tree for this example - "aabb", you will be able to understand everything clearly 
    void solve(int index, string& s, vector<string>& path, vector<vector<string> >& ans) 
    {  
        if(index == s.size()) {
            ans.push_back(path);
            return;
        }
        
        string temp = "";
        for(int i = index; i < s.size(); ++i) 
        {   
            temp += s[i];
            if(isPalindrome(s, index, i)) 
            {
                path.push_back(temp);
                solve(i+1, s, path, ans);
                path.pop_back();
            }
        }
    }

    vector<vector<string>> partition(string s) {
        vector<vector<string>> ans;
        if(s.empty()) 
            return ans;
        
        vector<string>path;
        solve(0, s, path, ans);
        
        return ans;
    }
};
Approach - 2 : Recursion & Backtracking [ C++ Code ]

Time Complexity : O(2^N * (N + N)) ~ O(2^N * N).

  • O(2^N) : Represents the number of recursive calls in the tree. For each character, there are two choices : either make a cut or don't, leading to 2^N recursive calls.
  • O(N) : In each recursive call, we check whether a substring is a palindrome, which takes O(N) time. Additionally, we perform substring creation which also takes O(N). So for each recursive call, the palindrome check and substring creation together take O(N) time.

Space Complexity : O(2^N * N), For each partition, we could have up to N substrings, where N is the length of the string s. This happens in the worst case where every single character is considered as a palindrome substring. For example, "a|a|b|b" would have 4 substrings if the string is "aabb". So, the total space required to store all partitions is the product of the number of partitions 2^N and the maximum number of substrings in a partition N.

class Solution {
public:
    
    bool isPalindrome(string& s, int i, int j) 
    {
        while(i <= j) {
            if(s[i++] != s[j--])
                return false;
        }
        return true;
    }
    
    // Draw recursive tree for this example - "aabb", you will be able to understand everything clearly 
    void solve(int index, string& s, vector<string>& path, vector<vector<string> >& ans) 
    {  
        if(index == s.size()) {
            ans.push_back(path);
            return;
        }
        
        for(int i = index; i < s.size(); ++i) 
        {
            if(isPalindrome(s, index, i)) 
            {
                path.push_back(s.substr(index, i - index + 1));// start index , len
                solve(i+1, s, path, ans);
                path.pop_back();
            }
        }
    }

    vector<vector<string>> partition(string s) {
        vector<vector<string>> ans;
        if(s.empty()) 
            return ans;
        
        vector<string>path;
        solve(0, s, path, ans);
        
        return ans;
    }
};

10. K'th Permutation Sequence
Problem link : https://leetcode.com/problems/permutation-sequence/

Approach - 1 : Brute Force (Gives TLE) [ C++ Code ]

Time Complexity : O(n * n!) + O(n!logn!), The recursion takes O(N!) time because we generate every possible permutation and another O(N) time is required to make a deep copy and store every sequence in the data structure. Also, O(N!Log N!) time required to sort the all permutations.
Space Complexity : O(n * n!) , O(n) space taken by each permutation.

class Solution{
public:
        
    // function to generate all possible permutations of a string
    void solve(string & s, int index, vector<string>&res) 
    {
        if (index == s.size()) {
            res.push_back(s);
            return;
        }
            
        for (int i = index; i < s.size(); i++) 
        {
            swap(s[i], s[index]);
            solve(s, index + 1, res);
            swap(s[i], s[index]);
        }
    }
        
    string getPermutation(int n, int k) 
    {
        string s;
        vector<string>res;
        // create string
        for (int i = 1; i <= n; i++) {
            s.push_back(i + '0');
        }
        solve(s, 0, res);
        // sort the generated permutations
        sort(res.begin(), res.end());
        //make k 0-based indexed to point to kth sequence
        return res[k-1];
    }
};
Approach - 2 : Mathematics [ C++ Code ]

Time Complexity : O(N*N), We are placing N numbers in N positions. This will take O(N) time. For every number, we are reducing the search space by removing the element already placed in the previous step. This takes another O(N) time.
Space Complexity : O(N), We are storing the numbers in a vector.

// Dry run for N=4, K=17, then you will understand after dry run
class Solution {
public:
    
    string getPermutation(int n, int k) 
    {    
        int fact = 1; // stores (n-1)!
        vector<int>numbers;
        for (int i = 1; i < n; i++) // 1 to n-1
        { 
            fact = fact * i;
            numbers.push_back(i);
        }
        numbers.push_back(n);
        string ans = "";
        k = k - 1; // 0th based indexing 
        
        while (true) 
        {
            ans = ans + to_string(numbers[k / fact]);
            numbers.erase(numbers.begin() + (k / fact));
            if (numbers.size() == 0) 
            {
                break;
            }

            k = k % fact;
            fact = fact / numbers.size();
        }
        return ans;
    }
};

11. N-Queens Problem
Problem link : https://leetcode.com/problems/n-queens/description/

Approach - 1 : Brute Force [ C++ Code ]

Time Complexity : O(N!*3*N), Since we have N choices in the first column, then N-1 choices in the second column and so on so the overall complexity become O(N!), 3*N is taken by isSafe() function eveytime.
Space Complexity : O(N*N), Just the board and if we consider auxiliary recursive stack space, so maximum recursion depth is N, requiring O(N) space.

// Brute Force Approach - passed all cases, not giving any TLE, but still we will optimize this. 
class Solution {
public:
    
    bool isSafe(vector<string>&board, int row, int col, int n)
    {
        int duprow = row;
        int dupcol = col;
        
        // check upper diagonal 
        while (row >= 0 && col >= 0) {
            if (board[row][col] == 'Q') return false;
            row--, col--;
        }
        // check left direction in a row
        row = duprow;
        col = dupcol;
        while (col >= 0) {
            if (board[row][col] == 'Q') return false;
            col--;
        }

        // check lower diagonal
        row = duprow;
        col = dupcol;
        while (row < n && col >= 0) {
            if (board[row][col] == 'Q') return false;
            row++, col--;
        }
        return true;
    }
    
    // filling queens columns wise
    void solve(int col, vector<string>&board, vector<vector<string>>&ans, int n)
    {
        if(col == n){
            ans.push_back(board);
            return;
        }
        
        for(int row = 0; row < board.size(); row++) { 
            if(isSafe(board, row, col, n)){
                
                board[row][col] = 'Q'; 
                solve(col + 1, board, ans, n);
                board[row][col] = '.';
            }
        }
    }
    
    // we have nxn board, and we need to place 'n' Queens there
    vector<vector<string>> solveNQueens(int n) {
        
        vector<vector<string>>ans;
        // vector<string>board(n);
        // string s(n, '.');
        // for (int i = 0; i < n; i++) {
        //     board[i] = s;
        // }
        vector<string>board(n, string(n, '.')); // creating empty nxn board
        solve(0, board, ans, n);
        return ans;
    }
};
Approach - 2 : Optimized (using 3 hash arrays) [ C++ Code ]

Time Complexity : O(N!), Since we have N choices in the first column, then N-1 choices in the second column and so on so the overall complexity become O(N!).
Space Complexity : O(N*N) + O(3*N), for board its O(N*N), and for hash array its O(3*N) and if we consider auxiliary recursive stack space, so maximum recursion depth is N, requiring O(N) space.

// Optimized code using Hashing (very easy), make improvement in isSafe() function.  
// In the previous isSafe() function : 
// - we need O(N) for a upper diagonal.
// - we need O(N) for the left direction in a row.
// - we need O(N) for lower diagonal. 
// Here we will use hashing to maintain a list to check whether that position can be the right one or not.
class Solution {
public:
    
    // filling queens columns wise
    void solve(int col, vector<string>&board, vector<vector<string>>&ans, vector<int>&lowerDiagonal, vector<int>&leftRow, vector<int>&upperDiagonal, int n)
    {
        if(col == n){
            ans.push_back(board);
            return;
        }
        
        for(int row = 0; row < board.size(); row++) { 
            if(upperDiagonal[(n-1) + col - row] == 0 && leftRow[row] == 0 && lowerDiagonal[col + row] == 0) {

                // mark
                lowerDiagonal[col + row] = 1;
                leftRow[row] = 1;
                upperDiagonal[(n-1) + col - row] = 1;

                board[row][col] = 'Q'; 
                solve(col + 1, board, ans, lowerDiagonal, leftRow, upperDiagonal, n);
                board[row][col] = '.';
                
                // unmark
                lowerDiagonal[col + row] = 0;
                leftRow[row] = 0;
                upperDiagonal[(n-1) + col - row] = 0;
            }
        }
    }
    
    // we have nxn board, and we need to place 'n' Queens there
    vector<vector<string>> solveNQueens(int n) {
        
        vector<vector<string>>ans;
        // vector<string>board(n);
        // string s(n, '.');
        // for (int i = 0; i < n; i++) {
        //     board[i] = s;
        // }
        vector<string>board(n, string(n, '.')); // creating empty nxn board
        vector<int>leftRow(n, 0), upperDiagonal(2*n-1, 0), lowerDiagonal(2*n-1, 0);
        solve(0, board, ans, lowerDiagonal, leftRow, upperDiagonal, n);
        return ans;
    }
};

12. Sudoku Solver
Problem link : https://leetcode.com/problems/sudoku-solver/

Approach : Recursion & Backtracking [ C++ Code ]

Time Complexity : O(9^(m)), in the worst case, for each cell in the nxn board, we have 9 possible numbers. where m is the number of empty cells. Here for a standard 9×9 Sudoku board, there are 81 cells in total. If most of the board is empty (m≈81), the worst-case complexity approaches O(9^81), which is extremely large. However, pruning via the isValid function reduces the number of invalid configurations significantly, especially as the board fills up.
Space Complexity : O(1), since we are refilling the given board itself, there is no extra space required, so constant space complexity. If we consider recursive stack space then recursion depth is at most m (the number of empty cells), resulting in O(m≈81) space.

class Solution {
public:
    
    // Most of the guys using 3 loops for checking of entire row, entire column, entire sub-Box
    // This takes just single iteration in which you will be able to check complete validity of '3 Sudoku Rules' 
    bool isValid(vector<vector<char>>& board, int row, int col, char c)
    {
        for(int i=0;i<9;i++)
        {
            // check row if there exist duplicate equal to 'c'
            if(board[row][i] == c)
                return false;
            // check col if there exist duplicate equal to 'c'
            if(board[i][col] == c)
                return false;
            /*
            check sub-Boxes if there exist duplicate equal to 'c'
            NOTE : Sub-Boxes numbered. from `0` to `8`
             ______ ______ ______  
            | SB-0 | SB-1 | SB-2 |    
            |______|______|______|
            | SB-3 | SB-4 | SB-5 |    
            |______|______|______|
            | SB-6 | SB-7 | SB-8 |    
            |______|______|______|    
            Example : 
            row = 4, col = 7, find sub box number where this cell lying
            Formula = (i/3)*3+j/3 = (4/3)*3+7/3 = 3 + 2 = 5
            
            There is a Sub-box number `5` corresponding to cell `(4,7)`
            Now Start Cell of sub-Box number `5`
            start_x = 3*(row/3) = 3*(4/3) = 3
            start_y = 3*(col/3) = 3*(7/3) = 6    
            */
            /*
               i : 0 1 2 3 4 5 6 7 8 
             i/3 : 0 0 0 1 1 1 2 2 2
             i%3 : 0 1 2 0 1 2 0 1 2
            */
            int start_x = 3*(row/3);
            int start_y = 3*(col/3);
            if(board[start_x + i/3][start_y + i%3] == c)
                return false;
        }   
        return true;
    }
    
    bool solve(vector<vector<char>>& board)
    {
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                
                // only fill empty cells
                if(board[i][j]=='.')
                {
                    // Try all possibilities from 1 to 9
                    for(char c ='1';c<='9';c++)
                    {
                        // check if current number does violate the rule or not 
                        if(isValid(board,i,j,c))
                        {
                            // update the board
                            board[i][j] = c;
                            // if valid move to next empty cell by calling the recursion for 'updated Board'
                            if(solve(board))
                                return true; // Whenever we get the valid solution,
                                            // Early return because we want 'ONE SOLUTION ; End up or Go back
                            
                            board[i][j] = '.';
                        }
                    }
                    // When each of the values from 1 to 9 does not satisfy a place (i,j), so return false
                    // and backtrack
                    return false;
                }
            }
        }
        
        // When your board is updated and filled completely i.e a one valid solution comes
        // Nothing is empty, just return "TRUE"
        return true;
    }
    
    void solveSudoku(vector<vector<char>>& board) {
        
        solve(board);
    }
};

13. M-Coloring Problem
Problem link : solve it on gfg [can't mention the link here]

Approach : Recursion & Backtracking [ C++ Code ]

Time Complexity : O(M^N), we have m color, and need to color N nodes.
Space Complexity : O(N), color array to keep track of which nodes are colored with x color.

class Solution{
public:
    
    // solve using backtracking
    bool isSafe(unordered_map<int,vector<int>>&g, vector<int>&color, int node, int n, int col)
    {
        for(auto nbr : g[node]){
            if(color[nbr] == col)
              return false;
        }
        return true;
    }
    
    bool solve(unordered_map<int,vector<int>>&g, vector<int>&color, int node, int m, int n)
    {
        if(node == n){
            return true;
        }
        
        for(int i=1;i<=m;i++){
            
            // is safe to color this current node with color 'i'
            if(isSafe(g, color, node, n, i))  
            {
                color[node] = i;
                if(solve(g,color,node+1,m,n))
                    return true;
                //backtrack
                color[node] = 0;
            }
        }
        return false;
    }
    
    // Remember you need to use "atmost M" colors not "exactly M" colors
    bool graphColoring(bool graph[101][101], int m, int n) {
        
        // form graph
        unordered_map<int,vector<int>>g;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(graph[i][j]==true){
                    g[i].push_back(j);
                    g[j].push_back(i);    
                }
            }
        }
        vector<int>color(n,0);
        return solve(g, color, 0, m, n);
    }    
};

14. Rat in Maze
Problem link : solve it on gfg [can't mention the link here]

Approach - 1 (DFS & Backtracking) [ C++ Code ]

Practice problem link : https://leetcode.com/problems/unique-paths-iii/

Time Complexity : O(4^(m*n)), because on every cell we need to try 4 different directions.
Space Complexity : O(m*n), Maximum Depth of the recursion tree (auxiliary space).

class Solution{
public:
    
    void dfs(vector<vector<int>> &g, int i, int j, int n, vector<string>&ans, string s)
    {
        if(i<0 or i >= n or j<0 or j >= n or g[i][j]==0) return;
        if(i==n-1 and j==n-1){
            ans.push_back(s);
            return;
        }
        g[i][j] = 0;
        
        dfs(g, i+1, j, n, ans, s + 'D');
        dfs(g, i-1, j, n, ans, s + 'U');
        dfs(g, i, j-1, n, ans, s + 'L'); 
        dfs(g, i, j+1, n, ans, s + 'R');
        // backtrack
        g[i][j] = 1;
    }
    
    vector<string> findPath(vector<vector<int>> &g, int n) {
        
        vector<string>ans;
        string s="";
        dfs(g, 0, 0, n, ans, s);
        return ans;
    }
};
Approach - 2 (DFS & Backtracking) [ C++ Code ]

Time Complexity : O(4^(m*n)), because on every cell we need to try 4 different directions.
Space Complexity : O(m*n), Maximum Depth of the recursion tree (auxiliary space).

class Solution {
public:

    void solve(vector<vector<int>> &g, int i, int j, int n, vector<pair<string, pair<int, int>>>&dir, vector<string>&ans, string s)
    {
        if(i==n-1 and j==n-1){
            ans.push_back(s);
            return;
        }
        
        g[i][j] = 0;    
        for(int k=0;k<4;k++)
        {
            int ni = i + dir[k].second.first;
            int nj = j + dir[k].second.second;
            if (ni >= 0 && ni < n && nj >= 0 && nj < n && g[ni][nj] == 1) {
                solve(g, ni, nj, n, dir, ans, s+dir[k].first);
            }
        }
        g[i][j] = 1;    
    }
    
    vector<string> findPath(vector<vector<int>> &g, int n) {
        
        vector<string>ans;
        // U:(-1,0), R:(0,1), D:(1,0), L:(0,-1)
        vector<pair<string, pair<int, int>>>dir = {{"U",{-1, 0}}, {"R",{0, 1}}, {"D",{1, 0}}, {"L",{0, -1}}}; 
        string s="";
        if(g[0][0] == 1)
            solve(g, 0, 0, n, dir, ans, s);
        return ans;
    }
};

15. Word Break - I
Problem link : https://leetcode.com/problems/word-break/

Approach : Recursion + memoization [ C++ Code ]

Time Complexity : O(N*N), In the worst case, there are O(N) recursive calls at each level of recursion, At each level of recursion, for a given index i, the code checks each substring from i to N-1, which takes O(N) time due to the substring creation and dictionary lookup.
Space Complexity : O(N + W), sum of the recursive stack, the dp array, and the dictionary storage, resulting in O(N + W).

class Solution {
public:
    
    // Do the segmentation of the string 's' based on strings present in the dictionary.
    // The same word in the dictionary can be reused multiple times in the segmentation.
    bool solve(int i, string &s, unordered_set<string>& dict, vector<int>&dp)
    {
        if(i == s.size()) return true;
    
        if(dp[i] != -1) return dp[i];
        
        string temp = "";
        for(int j = i;j < s.length();j++)
        {
            temp += s[j];
            if(dict.find(temp) != dict.end()) // check that word present in dictionary or not 
            {
                if(solve(j+1, s, dict, dp))
                    return dp[i] = true; 
                
            }
        }
        return dp[i] = false; 
    }
    
    bool wordBreak(string s, vector<string>& wordDict) 
    {
        unordered_set<string>set; // All the strings of wordDict are unique. i.e set of unique words
        // we use set here so that we can search word in it in O(1) complexity
        for(auto a : wordDict) 
            set.insert(a);
        vector<int> dp(s.size(), -1);    
        return solve(0, s, set, dp);
    }
};

16. Word break - II
Problem link : https://leetcode.com/problems/word-break-ii/description/
Practice problem : https://leetcode.com/problems/decode-ways/

Approach - 1 : Recursion & Backtracking (Efficient & Intuitive) [ C++ Code ]

Time Complexity : O((2^N) * N)

  • Recursive Calls : The function explores all possible partitions of s. For a string of length N, there are 2^(N-1) partitions in the worst case.
  • Substring Operations : Concatenation overhead (temp + s) : O(N) per recursive call in the worst case.

Space Complexity : O(N) + O(N) + O(W) ~ O(N)

  • Recursive Stack : The maximum depth of recursion is O(n), as each call shortens the string by one character in worst case.
  • Temporary Strings : Each recursive level maintains temporary strings like temp, contributing O(N) space per level.
  • Dictionary Space : O(W)
class Solution {
public:

    void solve(int i, string& str, unordered_set<string>& words, string temp, vector<string>&ans){

        if(i == str.size()){
            temp.pop_back();
            ans.push_back(temp);
            return;
        }

        string s = "";
        for(int j = i;j < str.size();j++){
            s += str[j];
            if(words.find(s) != words.end()){
                s += ' ';
                solve(j+1, str, words, temp+s, ans);
                s.pop_back();
            }
        }
    }

    vector<string> wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> words(wordDict.begin(),wordDict.end());
        vector<string> ans;
        solve(0, s, words, "", ans);
        return ans;
    }
};
Approach - 2 : Recursion & Backtracking [ C++ Code ]

Time Complexity : O((2^N) * N))

  • Recursive Calls : The function explores all possible partitions of s. For a string of length N, there are 2^(N-1) partitions in the worst case.
  • Substring Operations : Both concatenation and substring generation using s.substr contribute linearly within each recursive call, so Concatenation (O(N)) + Substring Creation (O(N)) = O(2N) ~ O(N).

Space Complexity : O(N) + O(N) + O(W) ~ O(N)

  • Recursive Stack : The maximum depth of recursion is O(n), as each call shortens the string by one character in worst case.
  • Temporary Strings : Each recursive level maintains temporary strings like temp, contributing O(N) space per level.
  • Dictionary Space : O(W)
class Solution {
public:
    
    void solve(unordered_set<string>&dict, string &s, vector<string>&ans, string tempAns)
    {
        if(s.length() == 0)
        {
            tempAns.pop_back(); // popback extra space " ".
            ans.push_back(tempAns);
            return;
        }
        
        for(int i = 0;i < s.length();i++)
        {
            string left = s.substr(0, i+1);
            if(dict.find(left) != dict.end()) // check that word present in dictionary or not 
            {
                string right = s.substr(i+1);
                solve(dict, right, ans, tempAns + left + " ");
            }
        }
    }
    
    vector<string> wordBreak(string s, vector<string>& wordDict) 
    {
        vector<string>ans;
        string temp = "";
        unordered_set<string>dict(wordDict.begin(), wordDict.end()); // for O(1) searching
        solve(dict, s, ans, temp);
        return ans;
    }
};

17. Word Search
Problem link : https://leetcode.com/problems/word-search/

Approach : Recursion & Backtracking [ C++ Code ]

Time Complexity : O(N * M * 4^k), The DFS may potentially visit each cell in the board multiple times. In the worst-case scenario, the DFS may attempt to visit all n * m cells for each of the word.size() characters, leading to a time complexity of O(n×m×4^k), where k is the length of the word.
Space Complexity : O(K), due to the recurson stack.

class Solution {
public:
    bool DFS(int i, int j, vector<vector<char>>& board, string& word, int index, int n, int m) {

        if (index == word.size()) return true;
        if (i < 0 || i >= n || j < 0 || j >= m || board[i][j] == '-')
            return false;

        if (board[i][j] != word[index]) // no match
            return false;

        char original = board[i][j];
        board[i][j] = '-'; // mark visited
        bool res = DFS(i + 1, j, board, word, index + 1, n, m) ||
                   DFS(i, j - 1, board, word, index + 1, n, m) ||
                   DFS(i, j + 1, board, word, index + 1, n, m) ||
                   DFS(i - 1, j, board, word, index + 1, n, m);
        board[i][j] = original; // backtracking
        return res;
    }

    bool exist(vector<vector<char>>& board, string word) {
        int n = board.size();
        int m = board[0].size();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                string temp = "";
                if (board[i][j] == word[0] && DFS(i, j, board, word, 0, n, m))
                    return true;
            }
        }
        return false;
    }
};

Thanks for Upvoting !
🙂 Feel free to comment and suggest any improvements !! ✅

Comments (4)