Print all subsets

- - -

- - 3

- 2 -

- 2 3

1 - -

1 - 3

1 2 -

1 2 3

package jan20;

public class AllSubsetArray {
    public static void main(String[] args) {

        // TC: O(1), SC: O(1)
        char[] arr = {'a', 'b', 'c'};  // Input array of length n = 3

        // TC: O(1), SC: O(1)
        int limit = (int) Math.pow(2, arr.length);  // Total subsets = 2^n

        // TC: Outer loop runs 2^n times => O(2^n), SC: O(1)
        for (int i = 0; i < limit; i++) {

            // TC: O(1), SC: O(n) — ans string can grow up to length n
            String ans = "";

            // TC: O(1), SC: O(1)
            int temp = i;

            // TC: Inner loop runs n times => O(n), SC: O(1)
            for (int j = arr.length - 1; j >= 0; j--) {

                // TC: O(1), SC: O(1)
                int remainder = temp % 2;

                // TC: O(1), SC: O(1)
                temp = temp / 2;

                // TC: O(1) string concat, SC: O(n) over all iterations
                if (remainder == 0)
                    ans = "- " + ans;
                else
                    ans = arr[j] + " " + ans;
            }

            // TC: O(1), SC: O(1)
            System.out.println(ans);  // Print one subset
        }
    }
}

📊 Complexity Table
Case
Time Complexity
Space Complexity
Explanation
Best
O(2ⁿ × n)
O(n)
Even in best case, the outer loop runs 2ⁿ times, and inner loop n times.
Average
O(2ⁿ × n)
O(n)
Same work regardless of actual input content.
Worst
O(2ⁿ × n)
O(n)
Full 2ⁿ iterations with O(n) string operations in each.