The idea to the solution for this medium LC problem is to use bit manipulation to iterate through all possible combination of bits and use this bits to generate the list of subsets. For example, a given array is [1,2,3], you could represent a subset of {1,2,3} as 111, {1,2} as 110, {1} as 100 and so on and so forth.
class Solution {
fun subsets(nums: IntArray): List<List<Int>> {
var output = mutableListOf<List<Int>>()
for(i in 0 until (1 shl nums.size)){
var list = mutableListOf<Int>()
for(x in 0 until nums.size){
if(i and (1 shl x) > 0) list.add(nums[x])
}
output.add(list)
}
return output
}
}
The outer loop will iterate from 0 to 1 shl nums.size or 8 (from 0001 to 1000). Then the inner loop iterates from 0 until 3. The second loop generates a binary sequence of 001, 010, 100 and 111 which basically acts like a selector. If i is 1 or 001, anding it to 001 will generate 1 so we add it to the list. If i is 3 or 011, the selectors 001 and 010 will both produce more then 0 so two indices 0 and 1 will be included in the list.
Runtime: 152 ms, faster than 98.41% of Kotlin online submissions for Subsets.
Memory Usage: 33.8 MB, less than 100.00% of Kotlin online submissions for Subsets.