78.subsets.md

78. Subsets

private val results = mutableListOf<List<Int>>()

fun subsets(nums: IntArray): List<List<Int>> {
    for (size in 0..nums.size) {
        dfs(nums, 0, size, ArrayDeque<Int>())
    }
    return results    
}

private fun dfs(nums: IntArray, startIndex: Int, size: Int, combination: ArrayDeque<Int>) {
    if (size == 0) {
        results.add(ArrayList<Int>(combination))
        return
    }
    
    for (i in startIndex until nums.size) {
        // Prune
        if (nums.size - i < size) break

        combination.addLast(nums[i])
        dfs(nums, i + 1, size - 1, combination)
        // Backtracking
        combination.removeLast()
    }
}

• Time Complexity: O(n * 2^n), n for iterating each size, 2^n for subsets.
• Space Complexity: O(n), we use at most O(n) space for DFS.