Power Set (All Subsets)

# Power Set (All Subsets) ## Difficulty Medium ## Tags `bit manipulation`, `recursion`, `backtracking` ## Problem Statement Given a string containing unique characters, return all possible subsets (the power set) of its characters. The solution must include the empty set. ## Constraints - 0 ≤ s.length ≤ 10 - All characters in `s` are unique. - The solution set must not contain duplicate subsets. - Return subsets in any order. ## Signatures ### Python ```python def find_subsets(s: str) -> List[str]: pass ``` ### Java ```java public class Solution { public List<String> find_subsets(String s) { return null; } } ``` ### Csharp ```csharp public class Solution { public IList<string> find_subsets(string s) { throw new NotImplementedException(); } } ``` ### Cpp ```cpp class Solution { public: vector<string> find_subsets(string s) { } }; ``` ### C ```c vector<char*> find_subsets(char* s) { } ``` ### Ruby ```ruby def find_subsets(s) end ``` ### Perl ```perl sub find_subsets { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def find_subsets(s: String): List[String] = { } } ``` ### Haskell ```haskell find_subsets :: ... -> ... find_subsets args = undefined ``` ### Clojure ```clojure (defn find_subsets [s] ) ``` ### Scheme ```scheme (define (find_subsets s) ) ``` ## Examples ### Example 1 **Input:** ``` s = "abc" ``` **Output:** ``` ["", "a", "b", "c", "ab", "ac", "bc", "abc"] ``` **Explanation:** All 2³ = 8 subsets of 3 characters. ### Example 2 **Input:** ``` s = "a" ``` **Output:** ``` ["", "a"] ``` ### Example 3 **Input:** ``` s = "" ``` **Output:** ``` [""] ``` **Explanation:** The power set of an empty set is a set containing only the empty set. ## Hints ### Approach 1: Bit Manipulation 1. For a string of length N, there are 2^N subsets. 2. Iterate from 0 to 2^N - 1. 3. For each number, check which bits are set. 4. If bit j is set, include character at index j in the subset. ### Approach 2: Recursion 1. For each character, make two choices: include it or exclude it. 2. Recurse on the remaining characters. 3. Base case: when no characters remain, add current subset to result.