Subsets Pattern

import java.util.*;
public class Subsets {
    // Generate all subsets (BFS approach)
    public static List<List<Integer>> findSubsets(int[] nums) {
        List<List<Integer>> subsets = new ArrayList<>();
        subsets.add(new ArrayList<>());  // Start with empty subset
        for (int num : nums) {
            // Take all existing subsets and add current number to them
            int size = subsets.size();
            for (int i = 0; i < size; i++) {
                // Create new subset from existing one
                List<Integer> newSubset = new ArrayList<>(subsets.get(i));
                newSubset.add(num);
                subsets.add(newSubset);
            }
        }
        return subsets;
    }
    // Alternative: Recursive (DFS) approach
    public static List<List<Integer>> findSubsetsRecursive(int[] nums) {
        List<List<Integer>> subsets = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), subsets);
        return subsets;
    }
    private static void backtrack(int[] nums, int start,
                                   List<Integer> current,
                                   List<List<Integer>> subsets) {
        // Add current subset
        subsets.add(new ArrayList<>(current));
        // Try adding each remaining number
        for (int i = start; i < nums.length; i++) {
            current.add(nums[i]);  // Choose
            backtrack(nums, i + 1, current, subsets);  // Explore
            current.remove(current.size() - 1);  // Unchoose (backtrack)
        }
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        System.out.println("BFS approach:");
        System.out.println(findSubsets(nums));
        System.out.println("\nDFS approach:");
        System.out.println(findSubsetsRecursive(nums));
        // Both output: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]
    }
}

import java.util.*;
public class SubsetsWithDuplicates {
    public static List<List<Integer>> findSubsets(int[] nums) {
        // Sort to handle duplicates
        Arrays.sort(nums);
        List<List<Integer>> subsets = new ArrayList<>();
        subsets.add(new ArrayList<>());
        int startIndex = 0;
        int endIndex = 0;
        for (int i = 0; i < nums.length; i++) {
            startIndex = 0;
            // If current element is duplicate, only add to subsets
            // created in previous iteration
            if (i > 0 && nums[i] == nums[i - 1]) {
                startIndex = endIndex + 1;
            }
            endIndex = subsets.size() - 1;
            // Add current number to existing subsets
            for (int j = startIndex; j <= endIndex; j++) {
                List<Integer> newSubset = new ArrayList<>(subsets.get(j));
                newSubset.add(nums[i]);
                subsets.add(newSubset);
            }
        }
        return subsets;
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, 2};
        List<List<Integer>> subsets = findSubsets(nums);
        System.out.println("Subsets: " + subsets);
        // Output: [[], [1], [2], [1,2], [2,2], [1,2,2]]
        // Note: No duplicate [2] subsets!
    }
}

import java.util.*;
public class Permutations {
    public static List<List<Integer>> findPermutations(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Queue<List<Integer>> permutations = new LinkedList<>();
        permutations.add(new ArrayList<>());
        // Process each number
        for (int num : nums) {
            int n = permutations.size();
            // Take each existing permutation
            for (int i = 0; i < n; i++) {
                List<Integer> oldPermutation = permutations.poll();
                // Insert current number at every possible position
                for (int j = 0; j <= oldPermutation.size(); j++) {
                    List<Integer> newPermutation = new ArrayList<>(oldPermutation);
                    newPermutation.add(j, num);
                    // If permutation is complete, add to result
                    if (newPermutation.size() == nums.length) {
                        result.add(newPermutation);
                    } else {
                        permutations.add(newPermutation);
                    }
                }
            }
        }
        return result;
    }
    // Alternative: Recursive approach with backtracking
    public static List<List<Integer>> findPermutationsRecursive(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, new ArrayList<>(), result);
        return result;
    }
    private static void backtrack(int[] nums, List<Integer> current,
                                   List<List<Integer>> result) {
        // Base case: permutation is complete
        if (current.size() == nums.length) {
            result.add(new ArrayList<>(current));
            return;
        }
        // Try adding each number that's not already in current permutation
        for (int num : nums) {
            if (current.contains(num)) continue;  // Skip if already used
            current.add(num);  // Choose
            backtrack(nums, current, result);  // Explore
            current.remove(current.size() - 1);  // Unchoose
        }
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        System.out.println("Permutations:");
        System.out.println(findPermutations(nums));
        // Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
    }
}