LeetCode 39. 组合和 - 如何避免重复

Question

我正在做leetcode 39.组合和。:

给定一组不同整数

candidates

和一个

target

整数目标，返回

candidates

的所有唯一组合的列表，其中所选数字总和为

target

。您可以按任何顺序返回组合。

可以从candidates和

无限次

中选择相同数。如果至少一个所选数字的频率不同，则两个组合是唯一的。

保证，对于给定输入，总和为

target

的唯一组合数量少于

150

组合。

限制

• 1 <= candidates.length <= 30

• 1 <= candidates[i] <= 200

• candidates

  的所有元素都是不同。

• 1 <= target <= 500

我能够编写以下代码：

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        output = []
        
        def backtrack(currNbr, comb):
            if currNbr == 0:
                output.append(comb.copy())
                return
            elif currNbr < 0:
                return
            
            for nbr in candidates:
                comb.append(nbr)
                currNbr = currNbr - nbr
                backtrack(currNbr, comb)
                comb.pop()
                currNbr = currNbr + nbr
                
        backtrack(target, comb = [])  
        
        return output
        

但是，我无法对其进行排序以避免重复。我在网上看到了一些解决方案，但它们似乎都使用索引

i

。谁能向我解释一下如何更改我的代码以避免重复？

Answer 1

是的，使用索引

i

是很常见的。这是因为一旦您迭代到

nbr

的下一个

combinations

，在更深的递归中的任何位置，都应该从

combinations

中选择一个条目，该条目位于此处所选条目之前。

您可以在没有

i

 的情况下执行此操作，而是传递 

combinations

 的缩短副本，其中仅包含仍允许选择的条目。

有几种方法可以做到这一点。当您还想缩短列表时，应该注意正确迭代列表。此外，

pop()

比

pop(0)

更有效。所以我选择使用 

reversed

 以相反的顺序迭代：

        def backtrack(candidates, currNbr, comb):   # Extra parameter
            if currNbr == 0:
                output.append(comb.copy())
                return
            elif currNbr < 0:
                return
            
            for nbr in reversed(candidates):  #  Reversed iteration 
                comb.append(nbr)
                backtrack(candidates[:], currNbr - nbr, comb)  # Pass a copy
                comb.pop()
                candidates.pop()  # The discarded element should not be used 
                
        backtrack(candidates, target, comb = [])  #  Extra argument

Answer 2

🚀 问题解决者的激动人心的消息！ 🚀 您准备好解决具有挑战性的编码问题并提高解决问题的技能了吗？与 Coding Samvaad 一起踏上算法和数据结构世界的激动人心的旅程！ 🔍 问题聚焦：组合和（LeetCode 上的问题＃39）在我们最新的视频中，我们揭开了组合和问题的复杂性，这是一个经典的算法挑战，测试您找到总和达到给定目标的所有可能候选组合的能力.

🎥 立即观看：

https://youtu.be/N_LJFBJJKeQ?si=26uo2LDpRgAzG4GA

在这个综合教程中，我们深入研究问题解决过程，探索递归技术和回溯策略来制定有效的解决方案。请跟随我们剖析问题陈述、分析基本概念并逐步实施解决方案。

💡关键要点： • 更深入地了解递归和回溯算法。 • 了解如何自信地处理复杂的编码问题。 • 增强您解决问题的能力和算法思维。

加入我们，揭开组合和问题的神秘面纱，并揭开掌握数据结构和算法的秘密。不要忘记点赞、分享和订阅 Coding Samvaad，以获取更多有洞察力的教程和编码挑战！ 让我们一起踏上这段编码冒险之旅，将我们的编程技能提升到新的高度！ 💻✨

订阅 -

https://www.youtube.com/channel/UCzMjtSYQiCK_jNEAo9fj0Sg?sub_confirmation=1

#Recursion #CombinationSum #LeetCode #ProblemSolving #CodingChallenge #DataStructures #Algorithms #ProgrammingTutorial #CodingSamvaad