Skip to main content

Subsets Problems

Formulae​

  • all possible subsets (Power set): 2n
caution

  • Time complexity

    • of any problem related to permulations is at least 2n

  • Space complexity

    • The space complexity is O(n). This space will be used to store the recursion stack. Since our recursive algorithm works in a depth-first fashion, which means, we can't have more than n recursive calls on the call stack at any time.

All subsets - Power sets [repititions not considered]​

Leetcode: subsets-1

  • all possible subsets (Power set): 2n

    Power set is all possible combinations of all possible lengths, from 0 to n.

for loop without return​

add_subset_toResult ⏩ adding_CurrentElement_to_Subset ⏩ call_RecursiveFunction ⏩ remove_added_element_from_Subset

  • for loop to get each element and then building the subset from that element onwards and I don't for index=i to go back to the previous index , Thus I am starting for loop with curent position i=pos
    • adding currenElement to subset directly without thinking of condition: NOT Adding element becoz the the subset without current element is already added by ans.emplace_back(sub); on every recursive call before entering the for loop.
      • Thus, for loop only have to think about adding elements to subset becoz subset without adding elements is already done outside for loop.
    • the for loop alone will create the subset, So I just have to add the subset to my result. I can add the subset to result anywhere outside for loop either after for loop or before doesn't matter.
    • as the for loop creates the subset by itselt alone, 💣💣 so I can't use return because then everytime the recursiveFunction is called: I will reuturn💣💣
  • generate(sub, nums, i+1); becoz the for loop will starting making the subset from i=pos , and then subsets will keep on making by i+1
add_subset_toResult ⏩ adding_CurrentElement_to_Subset ⏩ call_RecursiveFunction ⏩ remove_added_element_from_Subset 
    void generate(vector<int>& sub, vector<int> nums, int pos) {
        ans.emplace_back(subset);   // subset without without adding currentElement is being added here, so for loop only thinks of subset without currentElement
         // return is not being used
        for (int i = pos; i<nums.size(); i++) {     // for loop starts with current `pos`
            sub.emplace_back(nums.at(i));
            generate(sub, nums, i+1);   // "i+1" is called NOT `pos+1`
            sub.pop_back();
        }

    /* add the subset to result anywhere outside for loop */
        // ans.emplace_back(sub);  // `return` is not being used

    }
Image explaining for loop used with subset

`for` loop used with **subset**

two recursive calls​

backtracking used
vector<vector<char>> subsets;

void generate(vector<char> &subset, vector<char> &nums, int k)
{
    if (k == nums.size())
    {
        subsets.emplace_back(subset);
        return;
    }
    generate(subset, nums, k + 1);      // generating subset WITHOUT adding the current element to the subset
    subset.emplace_back(nums.at(k));    // adding current element to the subset
    generate(subset, nums, k + 1);      // generating subset AFTER adding the current element to the subset
    subset.pop_back();                  // removing added element from subset , So as to get back to Original state
}

int main() {
    // nums given
    // subset = empty

    generate(subset, nums, 0);

    // print the subsets now
}
Code for the Explanation Program

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

#define endl '\n'
#define ll long long

vector<vector<char>> subsets;

void print()
{
    cerr << "  ...all subsets: { ";
    for (auto &el : subsets)
    {
        cerr << "(";
        for (auto &el2 : el)
        {
            cerr << el2 << ",";
        }
        cerr << ")  ";
    }
    cerr << "}\n";
}

void subprint(vector<char> &subset)
{
    cerr << "(";
    for (auto el : subset)
    {
        cerr << el << ",";
    }
    cerr << ")";
}

void generate(vector<char> &subset, vector<char> &nums, int k)
{
    cerr << "k=" << k << ": curSubset:";
    if (subset.empty())
    {
        cerr << "( )";
    }
    else
    {
        subprint(subset);
    }

    if (k == nums.size())
    {
        subsets.emplace_back(subset);
        cerr << " ⏩ adding currSubset: ";
        subprint(subset);
        cerr << " ⏩  making:";
        print();
        return;
    }

    cerr << "\n..generating at ` (k+1)=(" << k + 1 << ") ` for k=" << k << "... .\n";
    generate(subset, nums, k + 1);
    cerr << "\n↪️ after previous generate() at k=" << k + 1 << ",   k gets back to '" << k << "' __.\n";

    cerr << "➕⊕ adding element '" << nums.at(k) << "' now curSubset: ";
    subset.emplace_back(nums.at(k));
    subprint(subset);
    cerr << "\n..generating at ` (k+1)=(" << k + 1 << ") ' for k=" << k << "...\n";
    generate(subset, nums, k + 1);

    subset.pop_back();
    cerr << "❌__removed element: '" << nums.at(k) << "' at k=" << k << endl
         << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<char> nums(n);
    for (auto &el : nums)
    {
        cin >> el;
    }
    vector<char> subset;

    generate(subset, nums, 0);

    cout << "  ...subsets: {";
    for (auto &el : subsets)
    {
        for (auto &el2 : el)
        {
            cout << el2 << ",";
        }
        cout << endl;
    }
    cout << "}\n";

    return 0;
}
tip
Explanation of ⏫ above Code

k=0: curSubset:( )
..generating at ` (k+1)=(1) ` for k=0... .
k=1: curSubset:( )
..generating at ` (k+1)=(2) ` for k=1... .
k=2: curSubset:( )
..generating at ` (k+1)=(3) ` for k=2... .
k=3: curSubset:( ) ⏩ adding currSubset: () ⏩  making:  ...all subsets: { ()  }

↪️ after previous generate() at k=3,   k gets back to '2' __.
➕⊕ adding element 'C' now curSubset: (C,)
..generating at ` (k+1)=(3) ' for k=2...
k=3: curSubset:(C,) ⏩ adding currSubset: (C,) ⏩  making:  ...all subsets: { ()  (C,)  }
❌__removed element: 'C' at k=2


↪️ after previous generate() at k=2,   k gets back to '1' __.
➕⊕ adding element 'B' now curSubset: (B,)
..generating at ` (k+1)=(2) ' for k=1...
k=2: curSubset:(B,)
..generating at ` (k+1)=(3) ` for k=2... .
k=3: curSubset:(B,) ⏩ adding currSubset: (B,) ⏩  making:  ...all subsets: { ()  (C,)  (B,)  }

↪️ after previous generate() at k=3,   k gets back to '2' __.
➕⊕ adding element 'C' now curSubset: (B,C,)
..generating at ` (k+1)=(3) ' for k=2...
k=3: curSubset:(B,C,) ⏩ adding currSubset: (B,C,) ⏩  making:  ...all subsets: { ()  (C,)  (B,)  (B,C,)  }
❌__removed element: 'C' at k=2

❌__removed element: 'B' at k=1


↪️ after previous generate() at k=1,   k gets back to '0' __.
➕⊕ adding element 'A' now curSubset: (A,)
..generating at ` (k+1)=(1) ' for k=0...
k=1: curSubset:(A,)
..generating at ` (k+1)=(2) ` for k=1... .
k=2: curSubset:(A,)
..generating at ` (k+1)=(3) ` for k=2... .
k=3: curSubset:(A,) ⏩ adding currSubset: (A,) ⏩  making:  ...all subsets: { ()  (C,)  (B,)  (B,C,)  (A,)  }

↪️ after previous generate() at k=3,   k gets back to '2' __.
➕⊕ adding element 'C' now curSubset: (A,C,)
..generating at ` (k+1)=(3) ' for k=2...
k=3: curSubset:(A,C,) ⏩ adding currSubset: (A,C,) ⏩  making:  ...all subsets: { ()  (C,)  (B,)  (B,C,)  (A,)  (A,C,)  }
❌__removed element: 'C' at k=2


↪️ after previous generate() at k=2,   k gets back to '1' __.
➕⊕ adding element 'B' now curSubset: (A,B,)
..generating at ` (k+1)=(2) ' for k=1...
k=2: curSubset:(A,B,)
..generating at ` (k+1)=(3) ` for k=2... .
k=3: curSubset:(A,B,) ⏩ adding currSubset: (A,B,) ⏩  making:  ...all subsets: { ()  (C,)  (B,)  (B,C,)  (A,)  (A,C,)  (A,B,)  }

↪️ after previous generate() at k=3,   k gets back to '2' __.
➕⊕ adding element 'C' now curSubset: (A,B,C,)
..generating at ` (k+1)=(3) ' for k=2...
k=3: curSubset:(A,B,C,) ⏩ adding currSubset: (A,B,C,) ⏩  making:  ...all subsets: { ()  (C,)  (B,)  (B,C,)  (A,)  (A,C,)  (A,B,)  (A,B,C,)  }
❌__removed element: 'C' at k=2

❌__removed element: 'B' at k=1

❌__removed element: 'A' at k=0



all Subsets without Repitition Backtracking​

Leetcode: subsets-2

using SET - set<vector<int>> then Power Set generation​

using set<vector<int>> to store only unique subsets

using set<vector<int>> to store only unique subsets
class Solution {
public:
    set<vector<int>> ans;
    vector<int> sub;

    void boo(vector<int>& v, vector<int>& sub, int i) {
        if (i == v.size()) {
            ans.emplace(sub);
            return;
        }
        boo(v, sub, i+1);
        sub.emplace_back(v.at(i));
        boo(v, sub, i+1);
        sub.pop_back();
    }

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<int> v(nums.begin(), nums.end());
        boo(v, sub, 0);
        vector<vector<int>> sol(ans.begin(), ans.end());


        return sol;
    }
};

for loop without return​

just sort() add a condition inside for : rest is same as PowerSet generation

sort ⏩ add_subset_toResult ⏩ checkIfDuplicate ⏩ adding_CurrentElement_to_Subset ⏩ call_RecursiveFunction ⏩ remove_added_element_from_Subset

  • sort() first
  • for loop to get each element and then building the subset from that element onwards and I don't for index=i to go back to the previous index , Thus I am starting for loop with curent position i=pos
    • adding currenElement to subset directly without thinking of condition: NOT Adding element becoz the the subset without current element is already added by ans.emplace_back(sub); on every recursive call before entering the for loop.
      • Thus, for loop only have to think about adding elements to subset becoz subset without adding elements is already done outside for loop.
    • the for loop alone will create the subset, So I just have to add the subset to my result. I can add the subset to result anywhere outside for loop either after for loop or before doesn't matter.
    • as the for loop creates the subset by itselt alone, 💣💣 so I can't use return because then everytime the recursiveFunction is called: I will reuturn💣💣
  • continue if duplicates found if(i != pos && nums[i] == nums[i-1])
  • generate(sub, nums, i+1); becoz the for loop will starting making the subset from i=pos , and then subsets will keep on making by i+1
sort ⏩ add_subset_toResult ⏩ checkIfDuplicate ⏩ adding_CurrentElement_to_Subset ⏩ call_RecursiveFunction ⏩ remove_added_element_from_Subset 
    vector<vector<int>> ans;
    void roo(vector<int>& subset, vector<int>& nums, int pos) {
        ans.emplace_back(subset);   // subset without without adding currentElement is being added here, so for loop only thinks of subset without currentElement
         // return is not being used

        for (int i = pos; i < nums.size(); i++) {       // for loop starts with current `pos`
            if(i != pos && nums[i] == nums[i-1]) {     // `i!=pos` so bcoz I need `nums[i-1]` & for getting `i-1`, I need `i>pos`
                continue;     // skips the rest of this particular iteration of `i` but other iterations will remains as they are
            }
            subset.emplace_back(nums.at(i));
            roo(subset, nums, i+1);     // "i+1" is called NOT `pos+1`
            subset.pop_back();
        }

    /* add the subset to result anywhere outside for loop */
        // ans.emplace_back(sub);  // return is not being used
    }

Subsets difference​

CSES Apple Division​

this is NOT BACKTRACKING

vector<ll> gl;

ll roo(vector<ll> v, ll i, ll s1, ll s2)
{
    if (i == v.size())
    {
        return abs(s2 - s1);
    }
    return min((roo(v, i + 1, s1 + v.at(i), s2)), roo(v, i + 1, s1, s2 + v.at(i)));
}

int main()
{
    ll n;
    cin >> n;
    vector<ll> v(n);
    for (auto &el : v)
    {
        cin >> el;
    }

    cout << roo(v, 0, 0, 0);

    return 0;
}