[Algo Rhythm🕺💃] LeetCode 78. Subsets

📚 Problem description

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

Note: The solution set must not contain duplicate subsets.

Example:
Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

 

🎯 Solution

1. Backtracking

class Solution {
    List<List<Integer>> answer = new ArrayList<>();
    
    public List<List<Integer>> subsets(int[] nums) {
        List<Integer> list = new ArrayList<>();
    
        backtrack(nums, list, 0, nums.length);
        
        return answer;
    }
    
    public void backtrack(int[] nums, List<Integer> list, int idx, int n) {        
        answer.add(new ArrayList<Integer>(list));
        
        for(int i = idx; i < n; i++) {
            list.add(nums[i]);
            backtrack(nums, list, i + 1, n);
            list.remove(list.size() - 1);
        }   
    }
}

 

2. Bit manipulation

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> answer = new ArrayList<>();
        
        for(int i = (1 << nums.length) - 1; i >= 0 ; i--) {
	// generate bitmask, from 1…1 to 00…0
            List<Integer> sub = new ArrayList<>();
            
            for(int j = 0; j < nums.length; j++) {
                if((i & (1 << j)) != 0) {
                    sub.add(nums[j]);
                }  
            }
            
            answer.add(sub);
        }
        
        return answer;
    }
}

 

🧐 Approach

1. Backtracking

Subset is one of typical example of backtracking. Backtracking is simply branching under specific condition.

If we think each element as node, branching condition is as below.

 

1. The node should not be visited.

2. The node should be on the right side of all the nodes in the list.

Here is illustrated example.

 

 

2. Bit manipulation

The idea is mapping each subset to a bitmask of length n, where 1 on ith position in bitmask means that nums[i] is in the subset, and 0 means it's not.

 

📖  What I learned