Subsets - Java Solution

1. Introduction

In this post, we'll explore how to generate all possible subsets of a given set of unique integers. This problem, often referred to as finding the power set, is a common question in computer science, particularly in the context of recursion and backtracking.

Problem

Given an integer array nums of unique elements, the task is to return all possible subsets of these elements. The solution must include all subsets, from the empty set to the full set, without containing any duplicate subsets.

2. Solution Steps

1. Use a backtracking approach to explore all possible combinations of the elements.

2. Start with an empty subset and at each step, add the next element to the current subset.

3. Recursively build subsets including and excluding the current element.

4. When the end of the array is reached, add the current subset to the list of subsets.

5. Return the list containing all subsets.

3. Code Program

import java.util.ArrayList;
import java.util.List;

public class Subsets {
    public static void main(String[] args) {
        int[] nums1 = {1, 2, 3};
        System.out.println(subsets(nums1)); // Example 1
        int[] nums2 = {0};
        System.out.println(subsets(nums2)); // Example 2
    }

    // Function to find all subsets of the given array
    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        backtrack(list, new ArrayList<>(), nums, 0);
        return list;
    }

    // Helper function for backtracking
    private static void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums, int start) {
        list.add(new ArrayList<>(tempList)); // Add the current subset
        for (int i = start; i < nums.length; i++) {
            tempList.add(nums[i]); // Include the current element
            backtrack(list, tempList, nums, i + 1); // Recurse with the current element included
            tempList.remove(tempList.size() - 1); // Exclude the current element and backtrack
        }
    }
}

Output:

Example 1: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
Example 2: [[], [0]]

Explanation:

1. subsets: This function initiates the process to find all subsets. It calls the backtrack function with the initial parameters.

2. backtrack: A recursive helper function that generates subsets. It adds the current subset (tempList) to the result list (list) at each step.

3. The function iterates over the elements, adding each element to tempList, and recursively calls itself to explore further.

4. After the recursive call, it removes the last element from tempList (backtracking) to explore subsets without that element.

5. The process continues until all subsets are generated and added to list.

6. The result is a list of all subsets of the given numbers, representing the power set.