90.subsets-ii.md

90. Subsets II

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

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

private fun dfs(nums: IntArray, startIndex: Int, size: Int, subset: ArrayDeque<Int>) {
    if (size == 0) {
        results.add(ArrayList<Int>(subset))
        return
    }

    for (i in startIndex until nums.size) {
        if (i > startIndex && nums[i] == nums[i - 1]) continue

        subset.addLast(nums[i])
        dfs(nums, i + 1, size - 1, subset)
        subset.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.