DSA

Power Set

Covers: Brute Force, Trie. Optimal — Time O(N^2), Space O(n).

August 8, 2026

Practice Link

Given a string s of length n, find all the possible non-empty subsequences of the string s in lexicographically-sorted order.

Brute Force Approach#

At each character, make a binary choice: include it in the current subsequence or skip it. Recursion through all such choices generates every subsequence. After all 2^n subsequences are collected, sort them for lexicographic order. This is correct but expensive due to the exponential generation and subsequent sort.

Create every possible subsequence using recursion and backtracking.

cpp

class Solution{
	public:
	
	    void solve(string s, vector<string> &res, int idx, string f)
	    {
	        if(idx >= s.length())
	        {
	            if(f.length() > 0)
	                res.push_back(f);
	            return;
	        }
	        
	        f += s[idx];
	        
	        solve(s, res, idx+1, f);
	        f.pop_back();
	        solve(s,res,idx+1, f);
	            
	    }
	
		vector<string> AllPossibleStrings(string s){
		    vector<string> res;
		    
		    solve(s, res,0, "");
		    sort(res.begin(), res.end());
		    return res;
		}
};

Time Complexity: O(2^n) + O(2^n log(2^n)) -> Sorting

Space Complexity: O(2^n) + O(n) -> recursion stack

Optimal Approach - Trie#

Process characters left to right, maintaining all subsequences built so far in prevSubsequences. For each new character ch, create new subsequences by appending ch to every existing subsequence (plus the single-character ch alone). Insert each new subsequence into a Trie to handle deduplication, then add it to the result. Because subsequences are built incrementally character by character, we avoid the full 2^n enumeration and naturally generate only those that end with the current character — bringing the generation from O(2^n) to O(n²).

cpp

class TrieNode{
public:
    bool isEnd;
    TrieNode* children[26];

    TrieNode(){
        isEnd = false;
        for(int i=0;i<26;i++)
            children[i] = false;
    }
};

class Trie{
public:
    TrieNode* root;
    
    Trie(){
        root = new TrieNode();
    }
    
    bool insert(string word) {
        TrieNode* curr = root;
        
        for(int i=0;i<word.length();i++){
            int idx = word[i]- 'a';
            if(curr->children[idx] == NULL){
                curr->children[idx] = new TrieNode();
            }
            curr = curr->children[idx];
        }
        
        curr->isEnd = true;
    }
};

class Solution{
public:
	vector<string> AllPossibleStrings(string s){
	    Trie trie;
        vector<string> res;
        vector<string> prevSubsequences;
        
        for (char ch : s) {
            vector<string> newSubsequences;
            newSubsequences.push_back(string(1, ch));

            for (const string& sub : prevSubsequences) {
                newSubsequences.push_back(sub + ch);
            }

            for (const string& sub : newSubsequences) {
                trie.insert(sub);
                res.push_back(sub);
            }

            prevSubsequences.insert(prevSubsequences.end(), newSubsequences.begin(), newSubsequences.end());
        }
        
        sort(res.begin(), res.end());

        return res;
	}
};

Time Complexity: O(N^2)

O(N^2) -> Generating subsequences

O(N^2) -> trie insertions

O(N^2 log N) -> sorting

DSAWord Search IITrie. Time O(m×k×4^L), Space O(L).DSADesign Add and Search Words Data StructureTrie. Space O(m).DSAPalindrome PairsTrie. Time O(n² * k), Space O(n²).

Brute Force Approach#

Optimal Approach - Trie#

Related articles