LeetCode "40. Combination Sum II"に、queueを使って挑んだけど失敗した話

LeetCodeの『40. Combination Sum II』に対する、私なりの挑戦です。結果はTime Limit Exceededです。今日も勝てなかったよ……！

問題

こちらから挑戦することができます。
https://leetcode.com/problems/combination-sum-ii/

候補となる数字（candidates）と目標となる数字（target）が与えられています。candidatesの中で候補となる数字の合計がtargetになるような、他とは異なる組み合わせをすべて見つけましょう。

candidatesの各数字は、組み合わせの中で一度だけ使うことができます。

気を付けてください：解答の集合には、重複する組み合わせを含んではいけません。

例1：

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

例2:

Input: candidates = [2,5,2,1,2], target = 5
Output:
[
[1,2,2],
[5]
]

制約

•1 <= candidates.length <= 100
•1 <= candidates[i] <= 50
•1 <= target <= 30

方針

•整数が要素の配列が与えられた時には、その順序を使う予定がないならば、その配列をソートしたほうがよいです。
•candidatesの何番目を使ったか/使っていないかを表現するのに、ビット演算が使えそうです。
ビット演算
https://docs.python.org/ja/3/library/stdtypes.html#bitwise-operations-on-integer-types
•探索を行うのに、再帰を使ったり、queueを使ったりできそう。昨日は再帰を使ったので、今回はqueueを使います。
今回は、問いが要求する組み合わせを全て列挙するので、LifoQueue（深さ優先探索）でもQueue（幅優先探索）でも変わらないはずです。

自分はqueueを使った探索の方法をYoutubeで学んだものの、その動画が見つかりません。
https://www.youtube.com/results?search_query=queue+python+search
皆様におかれましてはQiitaで良さそうな記事を探してください。

•探索の方針：
　回答として提出する入れ物（answer_comb）を用意する。
　candidatesの要素それぞれ（candidate）について、現在目標としている数値(cur_target)との差dを得る。
　dが負なら、絶望を胸に引き返す。
　dが0なら、cur_targetを形成する数字たちを、combに加える。
　dが正なら、dを新たな目標として、次の探索をする。
　…という探索を、最初はtargetを目標として開始する。
　すべての探索を終了したら、answer_combの中身を回答として提出する。

提出したコード

import queue

class Solution:
    def __init__(self):
        # 回答となる組み合わせを格納する入れ物を、集合として作ります。
        self.answer_comb = set()

    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        # 有意味である全ての範囲を探索するので、LifoQueue（深さ優先探索）でもQueue（幅優先探索）でも結果は同じはずです。
        q = queue.Queue()

        # 配列の順序が関係ないなら、ソートしたほうが楽です。
        candidates.sort(reverse=True)


        # ビットとして保存されているcandidatesの使用／不使用から、数字の組み合わせを得る関数。
        def wake_to_nums(wake):
            res = [] # 結果（result）として返されるリスト
            for i in range(len(candidates)):
                if 1 << i & wake:
                    res.append(candidates[i])
            return tuple(sorted(res)) #最終的な回答が重複を許さないので、setにしやすいようにtupleにします。

        def search():
            cur_target, wake = q.get()
            '''
            cur_target: 現在の探索の目標
            wake： 探索の痕跡。リストを使って表現したほうがわかりやすいものの、カッコつけたいのでビット演算を使用します。

            もし、どう頑張ってもcur_targetを作れそうにないなら、探索を打ち切ります。
            探索を打ち切るかどうかの判定のために、candidatesの、将来使用する見込みの数字を合計します。
            合計がcur_targetよりも小さいなら、探索を続ける意味がありません。

            r:現在使用している数字の最も右の数字の位置。wakeを2進数で書いたものの桁数-1。
            ''' 
            r = len(bin(wake)[2:]) -1 #bitで2進数の文字列を得ると、最初の「0b」が邪魔なので、[2:]でカットします。
            if wake == 0:
                r = -1 # wakeがまだ使用されていない場合には、後のために-1にします。

            #candidatesのrの次からの合計がcur_targetに満たなかったら、探索を打ち切ります。
            if sum(candidates[r + 1:]) < cur_target:
                #              ^^^^^
                # wakeが未使用の時にｒを-1にしておかないと、ここで不具合を起こします。
                return False # 後で何かに使えそうなので、特に意味なくFalseを返しておきます。

            # rより右の位置全てについて探索をします。
            for i, candidate in enumerate(candidates[r + 1:], start = r + 1):
                d = cur_target - candidate
                '''
                candidatesの要素それぞれ（candidate）について、現在目標としている数値(cur_target)との差dを得る。
                dが負なら、絶望を胸に引き返す。
              　dが0なら、cur_targetを形成する数字たちを、combに加える。
                dが正なら、dを新たな目標として、次の探索をする。

                cur_wake：現在の到達地点をビットで表現したもの
                '''

                cur_wake = wake | 1 << i

                if d < 0:
                    continue
                elif d == 0:
                    self.answer_comb.add(cur_wake)
                    continue
                elif d > 0:
                    q.put((d, cur_wake))



        # 探索のスタート地点をqに加えます。
        q.put((target, 0))

        # qが空でない限り、探索を続けます。
        while not q.empty():
            search()

        # ↓ここ、汚いですね！　どうにかしたい！
        return list(set(map(wake_to_nums, self.answer_comb)))

結果：Time Limit Exceeded

反省

Time Limit Exceededしたことよりも、enumerateで開始数字を指定し忘れたことのほうがミスとして大きかったです（このコードでは修正済み）。
enumerateの開始番号を指定しなかったことによる不具合を突き止められずに、時間を浪費してしまったため、就寝時間までにTime Limit Exceededを解決できなかったと考えています。
明日こそ勝つ！

追記

やはり、翌日時間をかけてみたら解けました。

import queue

class Solution:
    def __init__(self):
        # 回答となる組み合わせを格納する入れ物を、集合として作ります。
        self.answer_comb = set()
        '''
         candidates = [3, 2, 2, 1], target = 6が与えられたとき、配列の序数では[0, 1, 3]も[0, 2 ,3]も答えになりえます。
         しかし、どちらも額面で見ると[3, 2, 1]でしかありません。
         同じ額面のpathを踏んだか否かをチェックするために、pathを記録する集合を作ります。
         '''
        self.unique_path = set()

    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        # 有意味である全ての範囲を探索するので、LifoQueue（深さ優先探索）でもQueue（幅優先探索）でも結果は同じはずです。
        # 私はMagic; the Gatheringというカードゲームをプレイしてるので、Last in First outの「スタック」のほうがとっつきやすいです。
        q = queue.Queue()

        # 配列の順序が関係ないなら、ソートしたほうが楽です。
        candidates.sort(reverse=True)


        # ビットとして保存されているcandidatesの使用／不使用から、数字の組み合わせを得る関数。
        def wake_to_nums(wake):
            res = [] # 結果（result）として返されるリスト
            for i in range(len(candidates)):
                if 1 << i & wake:
                    res.append(candidates[i])
            return tuple(sorted(res)) #最終的な回答が重複を許さないので、setにしやすいようにtupleにします。

        def search():
            cur_target, wake = q.get()
            '''
            cur_target: 現在の探索の目標
            wake： 探索の痕跡。リストを使って表現したほうがわかりやすいものの、カッコつけたいのでビット演算を使用します。

            もし、どう頑張ってもcur_targetを作れそうにないなら、探索を打ち切ります。
            探索を打ち切るかどうかの判定のために、candidatesの、将来使用する見込みの数字を合計します。
            合計がcur_targetよりも小さいなら、探索を続ける意味がありません。

            r:現在使用している数字の最も右の数字の位置。wakeを2進数で書いたものの桁数-1。
            ''' 
            r = len(bin(wake)[2:]) -1 #bitで2進数の文字列を得ると、最初の「0b」が邪魔なので、[2:]でカットします。
            if wake == 0:
                r = -1 # wakeがまだ使用されていない場合には、後のために-1にします。

            #candidatesのrの次からの合計がcur_targetに満たなかったら、探索を打ち切ります。
            if sum(candidates[r + 1:]) < cur_target:
                #              ^^^^^
                # wakeが未使用の時にｒを-1にしておかないと、ここで不具合を起こします。
                return False # 後で何かに使えそうなので、特に意味なくFalseを返しておきます。

            # rより右の位置全てについて探索をします。
            for i, candidate in enumerate(candidates[r + 1:], start = r + 1):
                d = cur_target - candidate
                '''
                candidatesの要素それぞれ（candidate）について、現在目標としている数値(cur_target)との差dを得る。
                dが負なら、絶望を胸に引き返す。
              　dが0なら、cur_targetを形成する数字たちを、combに加える。
                dが正なら、dを新たな目標として、次の探索をする。

                cur_wake：現在の到達地点をビットで表現したもの
                '''

                cur_wake = wake | 1 << i
                comb = wake_to_nums(cur_wake) 

                if d < 0:
                    continue
                elif d == 0:
                    self.answer_comb.add(comb)
                    continue
                elif d > 0:
                    if comb not in self.unique_path:
                        q.put((d, cur_wake))
                        self.unique_path.add(comb)



        # 探索のスタート地点をqに加えます。
        q.put((target, 0))

        # qが空でない限り、探索を続けます。
        while not q.empty():
            search()

        return list(self.answer_comb)

最高に気持ちがいい！