78. Subsets

Description

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: nums = [1, 2, 3]

Output: [ [], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3] ]

Solutions

Solution 1

/**
 * Time complexity : O(N×2^N) to generate all subsets and then copy 
 *    them into output list.
 * Space complexity : O(N×2^N) to keep all the subsets of length N, 
 *    since each of N elements could be present or absent.
 */

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> resultList = new ArrayList<>();
        for(int k = 0; k <= nums.length; k++) {
            backtrack(resultList, new LinkedList<Integer>(), nums, 0, k);
        }
        return resultList;
    }
    private void backtrack(
        List<List<Integer>> resultList,
        LinkedList<Integer> currList,
        int[] nums,
        int start,
        int k
    ) {
        if(k == 0) {
            resultList.add(new ArrayList(currList));
        }
        for(int i = start; i < nums.length; i++) {
            currList.add(nums[i]);
            backtrack(resultList, currList, nums, i+1, k-1);
            currList.removeLast();
        }
    }
}

Follow up