Permutations & Subsets (Power Sets)

---

Permutations

1. Using Backtracking (Python)

Time Complexity: O(n·n!)

def permute(s, path=""):
    if not s:
        print(path)
        return
    for i in range(len(s)):
        permute(s[:i] + s[i+1:], path + s[i])

permute("123")

---

2. Using itertools.permutations (Python)

from itertools import permutations

for p in permutations("123"):
    print(''.join(p))

---

3. Using next_permutation (C++ STL)

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

int main() {
    string s = "123";
    sort(s.begin(), s.end());   // important
    do {
        cout << s << "\n";
    } while (next_permutation(s.begin(), s.end()));
    return 0;
}

---

4. Backtracking (C++)

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

void permute(string &s, int idx) {
    if (idx == s.size()) {
        cout << s << "\n";
        return;
    }
    for (int i = idx; i < s.size(); i++) {
        swap(s[idx], s[i]);
        permute(s, idx + 1);
        swap(s[idx], s[i]); // backtrack
    }
}

int main() {
    string s = "123";
    permute(s, 0);
}

---

5. Backtracking (Python, In-place)

def permute(s, idx=0):
    if idx == len(s):
        print(''.join(s))
        return
    for i in range(idx, len(s)):
        s[idx], s[i] = s[i], s[idx]
        permute(s, idx + 1)
        s[idx], s[i] = s[i], s[idx]

permute(list("123"))

---

Subsets / Power Sets

Time Complexity: O(n·2ⁿ) (There are 2ⁿ subsets, each takes O(n) to construct)

---

1. Bitmasking (C++)

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

int main() {
    string s = "123";
    int n = s.size();
    for (int mask = 0; mask < (1 << n); mask++) {
        string subset = "";
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                subset += s[i];
            }
        }
        cout << subset << "\n";
    }
}

---

2. Bitmasking (Python)

s = "123"
n = len(s)

for mask in range(1 << n):
    subset = ""
    for i in range(n):
        if mask & (1 << i):
            subset += s[i]
    print(subset)

---

3. Backtracking (C++)

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

void subsets(string &s, int idx, string curr) {
    if (idx == s.size()) {
        cout << curr << "\n";
        return;
    }
    // exclude
    subsets(s, idx + 1, curr);
    // include
    subsets(s, idx + 1, curr + s[idx]);
}

int main() {
    string s = "123";
    subsets(s, 0, "");
}

---

4. Backtracking (Python)

def subsets(s, idx, curr):
    if idx == len(s):
        print(curr)
        return
    subsets(s, idx + 1, curr)          # exclude
    subsets(s, idx + 1, curr + s[idx]) # include

subsets("123", 0, "")