Subsets 1

Given an array nums of n integers.Return sum of all subsets of the array nums.

void func(int ind, vector<int> &ans, vector<int> &nums, int sum)
    {
        if (ind == nums.size())
        {
            ans.push_back(sum);
            return;
        }
        func(ind + 1, ans, nums, sum + nums[ind]);
        func(ind + 1, ans, nums, sum);
    }
  vector<int> subsetSums(vector<int> &nums)
    {
        vector<int> ans;
        func(0, ans, nums, 0);
        return ans;
    }

Subsets 2

Given an integer array nums, which can have duplicate entries, provide the power set. Duplicate subsets cannot exist in the solution set. Return the answer in any sequence.

void func(int ind, vector<int> &temp, vector<vector<int>> &ans, vector<int> &nums)
    {
        if (ind == nums.size())
        {
            ans.push_back(temp);
            return;
        }
        temp.push_back(nums[ind]);
        func(ind + 1, temp, ans, nums);
        temp.pop_back();
        for (int i = ind + 1; i < nums.size(); i++) //skip duplicates
        {
            if (nums[i] != nums[ind])
            {
                func(i, temp, ans, nums);
                return;
            }
        }
        func(nums.size(), temp, ans, nums);
    }
    //Another better approach for backtracking (keep moving forward and skip duplicates)
    void solve(int idx, vector<int> &nums, vector<int> &temp,
               vector<vector<int>> &ans)
    {

        ans.push_back(temp);

        for (int i = idx; i < nums.size(); i++)
        {

            if (i > idx && nums[i] == nums[i - 1])
                continue;

            temp.push_back(nums[i]);
            solve(i + 1, nums, temp, ans);
            temp.pop_back();
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int> &nums)
    {
        // your code goes here
        vector<vector<int>> ans;
        vector<int> temp;
        sort(nums.begin(), nums.end());
        func(0, temp, ans, nums);
        return ans;
    }

Combinations

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].

Example:

// Input: n = 4, k = 2
// Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

 int end;
 void solve(int start, vector<vector<int>> &ans, vector<int> &temp, int n, int k)
    {
        if (n > end)
            return;
        if (temp.size() == k)
        {
            ans.push_back(temp);
            return;
        }
        for (int i = start; i <= n; i++)
        {
            temp.push_back(i);
            solve(i + 1, ans, temp, n, k);
            temp.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k)
    {
        end = n;
        vector<vector<int>> ans;
        vector<int> temp;
        solve(1, ans, temp, n, k);
        return ans;
    }