dfs 繰り返しなし

date: 2021-04-18 excerpt: dfs 繰り返しなしについて

dfs 繰り返しなしについて

概要

dfsですべての組み合わせを行うことは容易であるが、メモ化を用いずに、過去出現した要素を排除する方法
- tupleでsetに組み込むなどで対応できるが計算量に無駄が生じる
ソートされた対象で、dfsで選択時に、繰り返しを行う場合には避ける

具体例

def dfs(nums, ptr, s, ret):
    ret.append(s)
    n = len(nums)
    for nptr in range(ptr+1, n):
        # 同じ値が連続している場合には避ける
        if nptr > ptr + 1 and nums[nptr] == nums[nptr-1]:
            continue
        dfs(nums, nptr, s + [nums[nptr]], ret)

def solve(nums):
    ret = []
    dfs(nums, -1, [], ret)
    return ret


print(solve([1,2,2])) # [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]

# if文を入れないと以下の結果になる
# [[], [1], [1, 2], [1, 2, 2], [1, 2], [2], [2, 2], [2]]

参考

90. Subsets II/LeetCode