代码之家 › 专栏 › 技术社区 › Dawn17

生成数组的所有可能子集将返回空列表列表

recursion python

Dawn17 · 技术社区 · 7 年前

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """

        res = []
        self.backtrack(sorted(nums), 0, [], res)
        return res

    def backtrack(self, nums, idx, subset, res):
        res.append(subset)
        for i in range(idx, len(nums)):
            subset.append(nums[i])
            self.backtrack(nums, i + 1, subset, res)
            subset.pop()

正在练习面试。我应该生成给定列表的所有子集。例如,

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

然而,我的解决方案又回来了 [[],[],[],[],[],[],[],[]] 我也不知道为什么。我试图找出我的解决方案,但我不明白为什么子集会变成一个空列表。

可能的问题是什么?

2 回复 | 直到 7 年前

cdlane 7 年前

常见错误,您将实际指针保存到 subset 代替副本:

res.append(subset)

最后,你有一个重复的最终状态列表 子集 . 而是这样做:

res.append(list(subset))

把一份不会改变的拷贝强加给你。

仅供参考,我们可以用另一种方法来构建这个解决方案:

def subsets(self, numbers):

    def subsets_recursive(numbers, index, subset):
        result = [list(subset)]

        for i in range(index, len(numbers)):
            subset.append(numbers[i])
            result += subsets_recursive(numbers, i + 1, subset)
            subset.pop()

        return result

    return subsets_recursive(sorted(numbers), 0, [])

Christoforus Surjoputro 7 年前

您可以使用itertools组合来获得相同的结果:

from itertools import combinations
t = [list(combinations(nums, i)) for i in range(4)]
output = [list(j) for k in t for j in k]
#output: [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

推荐文章

RASEL MAHMUD · 为什么以及如何在is_even()函数内的IF条件中递归X变量在满足0后递增?[副本]

1 年前

MMedina · 将powershell应用于子文件夹

1 年前

YorSubs · Linux中遍历目录的时间不同方法[关闭]

1 年前