For a given array int[] nums = {1,2,3} generate all $2^n$ power sets where 𝑛 = length of given array.

Def$^n$: all possible subsets of a given set, including the empty set {} and the original set itself. The power set of a set 𝑆 is denoted by 𝑃(𝑆)

P(nums) = [ [ ],

                  [1], [2], [3], 

                  [1,2], [1,3], [2,3], 

                  [1,2,3] ]

It is advisable that you understand the difference b/w Subarray, Subsequence & Subset.

Motivation for the notes :

https://leetcode.com/problems/subsets/

https://www.geeksforgeeks.org/problems/power-set4302/1

There are broadly two approaches :

1. Bit Masking (iterative) 😷
2. Backtracking (recursive) ⭐
   1. Include-Exclude paradigm : here we see two variants & why we should use one over other
   2. For-loop paradigm : prefer this (reason at the end)

👉 Apply your learning :

How to generate all subsequences of length ≤ 𝑘 , where 𝑘 ≤ 𝑛 (length of the nums array). see solution

Practice problems for Susequence & Subset

Bit Masking

public class PowerSet {
    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        int totalSubsets = 1 << n; // 2^n
        List<List<Integer>> powerSet = new ArrayList<>();

        for (int mask = 0; mask < totalSubsets; mask++) {
            List<Integer> subset = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) { // Check if the i-th bit is set
                    subset.add(nums[i]);
                }
            }
            powerSet.add(subset);
        }
        return powerSet;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        PowerSet ps = new PowerSet();
        System.out.println(ps.subsets(nums));
    }
}

Back tracking

Some basics need to be made clear before proceeding with the code :