Problem statement:

Given a set with distinct elements, find all of its distinct subsets.

Example:

Input: [1, 5, 3]
Output: [], [1], [5], [3], [1,5], [1,3], [5,3], [1,5,3]

Solution backtracking DFS

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(nums, 0, result, new ArrayList<>());
    return result;
}

void backtrack(int[] nums, int start, List<List<Integer>> result, List<Integer> temp) {
    result.add(new ArrayList<>(temp));
    for (int i = start; i < nums.length; i++) {
        temp.add(nums[i]);
        backtrack(nums, i + 1, result, temp);
        temp.remove(temp.size() - 1);
    }
}

Solution backtracking BFS

public static List<List<Integer>> findSubsetsEducative(int[] nums) {
    List<List<Integer>> subsets = new ArrayList<>();
    // start by adding the empty subset
    subsets.add(new ArrayList<>());
    for (int currentNumber : nums) {
        // we will take all existing backtracking and insert the current number in them to create new backtracking
        int n = subsets.size();
        for (int i = 0; i < n; i++) {
            // create a new subset from the existing subset and insert the current element to it
            List<Integer> set = new ArrayList<>(subsets.get(i));
            set.add(currentNumber);
            subsets.add(set);
        }
    }
    return subsets;
}

Time complexity:

Since, in each step, the number of subsets doubles as we add each element to all the existing subsets, the time complexity of the above algorithm is O(2^N) where ‘N’ is the total number of elements in the input set. This also means that, in the end, we will have a total of O(2^N subsets

Space complexity:

O(N^2)

Approach:

dfs → backtracking, add in each step and start from index, and go to index + 1

bfs → add empty arr to result, then iterate through numbers and take result size and for all sets in result for the size create new set and add number there