C++ backtracking solution by making decision of choose or not to choose element


  • 0
    T

    class Solution {

    void combinations(vector<int> nums,vector<bool> visited,vector<vector<int>>& KchooseN,int k,int choose_count,int index)
    {
        if(choose_count == k)
        {   vector<int> vec;
            for(int i = 1;i <= nums.size();i++)
            {
                if(visited[i])
                    vec.push_back(nums[i - 1]);
            }
            KchooseN.push_back(vec);
            return;
        }
        
        if(index > nums.size())
            return;
        
        visited[index] = true;    // choose this index and increase the choose_count
        combinations(nums,visited,KchooseN,k,choose_count + 1,index + 1);
        visited[index] = false;   // don't choose this index and keep the choose_count as is
        combinations(nums,visited,KchooseN,k,choose_count,index + 1);
    }
    

    public:
    vector<vector<int>> combine(int n, int k) {

        vector<vector<int>> KchooseN;
        vector <int> nums;
        vector <bool> visited(n + 1,false);
        if(k > n)
            return KchooseN;
            
        for(int i = 1;i <= n;i++)
            nums.push_back(i);
            
        if(k == 0||k == n||n == 1)
        {
            KchooseN.push_back(nums);
            return KchooseN;
        }
        
        combinations(nums,visited,KchooseN,k,0,1);
        return KchooseN;
    }
    

    };


Log in to reply
 

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