ミュータブルなオブジェクトには気をつけよう

LeetCode

LeetCode - 78. Subsetsを解いているときに，エラーの原因がなかなかわからないという状況に陥りました．

問題としては，あるリストの全てのサブリストを要素とするリストをreturnせよという問題です．

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []
        def dfs(A, limit, index):
            if len(A) == limit:
                ans.append(A)
            else:
                for i in range(index+1, len(nums)):
                    A.append(nums[i])
                    dfs(A, limit, i)
                    A.pop()
            
        for i in range(len(nums)+1):
            dfs([], i, -1)
        return ans

最初，私はこのようなコードを書きました． しかし，[1, 2, 3]を入力としたとき，

input: [1, 2, 3]
output: [[], [], [], [], [], [], [], []]

となり，うまくいきませんでした．

なぜ，ansに[ ]しかappendされないのか．

そこで，

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []
        def dfs(A, limit, index):
            if len(A) == limit:
                ans.append(A)
                print(ans)
            else:
                for i in range(index+1, len(nums)):
                    A.append(nums[i])
                    dfs(A, limit, i)
                    A.pop()
            
        for i in range(len(nums)+1):
            dfs([], i, -1)
        return ans

とし，ansの動きを見てみると，

[[]]
[[], [1]]
[[], [2], [2]]
[[], [3], [3], [3]]
[[], [], [], [], [1, 2]]
[[], [], [], [], [1, 3], [1, 3]]
[[], [], [], [], [2, 3], [2, 3], [2, 3]]
[[], [], [], [], [], [], [], [1, 2, 3]]
[[], [], [], [], [], [], [], []]

となっていました． ansの中身のリストAが更新されてしまっている．

ansに毎度idが同じリストAをappendしてしまっており，リストはミュータブルなのでリストAが更新されるたび，ansの中身も更新されてしまっていた．

したがって，

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []
        def dfs(A, limit, index):
            if len(A) == limit:
                ans.append(A[:])
            else:
                for i in range(index+1, len(nums)):
                    A.append(nums[i])
                    dfs(A, limit, i)
                    A.pop()
            
        for i in range(len(nums)+1):
            dfs([], i, -1)
        return ans

のようにansにリストAのコピーをappendすればうまくいく．コピーすればidが異なるものとなるからです．

ミュータブルなものを配列に格納するときには，今後注意していこうと思いました．