More problems on Recursion

In this article we will be solving few more problems on recursion.

1) Combination sum I

class Solution {
public:

void combo(vector<vector<int>>&result, vector<int>a, vector<int>&v,int i, int n, int tot, int sum){
    if(i==n){
        if(tot==0) result.push_back(a); 
        return;
    }

if(v[i]<=tot){
a.push_back(v[i]);
combo(result,a,v,i,n,tot-v[i],sum);
a.pop_back();
}

combo(result,a,v,i+1,n,tot,sum);
}

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        combo(result, {}, candidates, 0, candidates.size(), target, target);
        return result;
    }
};

---

2) Combination sum II

class Solution {
public:

void combo(vector<vector<int>>&result, vector<int>a, vector<int>&v,int i, int tot){

if(tot==0){ result.push_back(a); return; }

for(int j=i; j<v.size(); j++){
    if(j>i && v[j]==v[j-1]) continue;
    if(v[j]>tot) break;
    a.push_back(v[j]);
    combo(result,a,v,j+1,tot-v[j]);
    a.pop_back();
}
}

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        sort(candidates.begin(),candidates.end());
        combo(result, {}, candidates, 0, target);
        return result;
    }
};

Note:

Even though we are using a function call in a for loop instead of 2 function calls, we are still following the take / not take approach.

Bcoz, in 2 calls, we take a element and call once, then remove element and call to next position.

In for loop + function call, we take a element and call once, and then remove element but for loop calls to next position.

3) Permutations of an array

[ Approach 1 ]

class Solution {
public:

    void func(vector<int>& v, vector<int> a, vector<bool> b, vector<vector<int>>& result){

        if(a.size()==v.size()){ result.push_back(a); return; }

        for(int i=0; i<v.size(); i++){
            if(! b[i]){ 
                a.push_back(v[i]); b[i]=true; 
                func(v,a,b,result); 
                a.pop_back(); b[i]=false;
            }
        }

    }

    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        func(nums, {}, vector<bool>(nums.size(), false), result);
        return result;
    }
};

[ Approach 2 ]

class Solution {
public:

    void swap(vector<int>&v, int x, int y){
        int temp=v[x];
        v[x]=v[y];
        v[y]=temp;
}


    void func(vector<int>& v, int start, vector<vector<int>>& result){
        if(start==v.size()-1){ result.push_back(v); return;}
        for(int i=start; i<v.size(); i++){
            swap(v,start,i);
            func(v,start+1,result);
            swap(v,start,i);
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        func(nums, 0, result);
        return result;
    }
};

---

4) Combination Sum III

class Solution {
public:
  void f(vector<vector<int>>& result, vector<int> a, int i, int k, int n){
    if(k==0 || n<=0){
        if(k==0 && n==0) result.push_back(a);
        return;
    }

    for(int j=i; j<10; j++){
        a.push_back(j);
        f(result, a, j+1, k-1, n-j);
        a.pop_back();
    }
  }


    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> result; 
        f(result,{},1,k,n);
        return result;
    }
};

---

5) Generate Parantheses

class Solution {
public:

    void f(vector<string>& result, string a, int n, int left){
        if(n==0){result.push_back(a); return;}
        string l="(", r=")";
        if(left<n) f(result, a+l, n, left+1);
        if(left>0) f(result, a+r, n-1, left-1);
    }


    vector<string> generateParenthesis(int n) {
        vector<string> result;
        f(result,"", n, 0);
        return result;
    }
};

---

6) Generate Binary Strings Without Consecutive 1s

class Solution {
public:

    void f(vector<string>& result, string a, int n){
        if(n==0){result.push_back(a); return;}
        f(result, a+"0", n-1);
        if(a.back()!='1') f(result, a+"1", n-1);
    }

    vector<string> generateBinaryStrings(int n) {
        vector<string> result;
        f(result, "", n);
        return result;
    }
};

---

7) Sudoku Solver

class Solution {
public:

    bool isValid(vector<vector<char>>& board, int x, int y){
        for(int i=0; i<9; i++) if(board[x][i]==board[x][y] && i!=y) return false;
        for(int i=0; i<9; i++) if(board[i][y]==board[x][y] && i!=x) return false;

        int rol=(x/3)*3, col=(y/3)*3;
        for(int i=rol; i<rol+3; i++){
            for(int j=col; j<col+3; j++){
                if(board[i][j]==board[x][y] && (i!=x || j!=y)) return false;
            }
        }

        return true;
    }

    bool tryEveryBoard(vector<vector<char>>& board){
        for(int i=0; i<9; i++){
            for(int j=0; j<9; j++){
                if(board[i][j]=='.'){
                    for(char k='1'; k<='9'; k++){
                        board[i][j]=k;
                        if(isValid(board, i, j) && tryEveryBoard(board)) return true;
                        board[i][j]='.';
                    }
                    return false;
                }
            }
        }
        return true; 
    }

    void solveSudoku(vector<vector<char>>& board) {
        tryEveryBoard(board);
    }
};

Note:

1) With tryEveryBoard, we are trying all possibilities in place.

2) In tryEveryBoard, if k is valid at board[i][j], then we go further and if tryEveryBoard also returns true, which means already a solution found, we stop there and return true.

3) We return false at tryEveryBoard after every possibility, coz if there’s further chance tryEveryBoard() will be called else we stop there ( early pruning ).

4) We finally return true as we found a solution.

---