我試圖建立一個解決方案來解決生成所有可能k的長度組合的問題n
例如：k = 4，n = 2
輸出 ：
[1, 1]
[1, 2]
[1, 3]
[1, 4]
[2, 1]
[2, 2]
[2, 3]
[2, 4]
[3, 1]
[3, 2]
[3, 3]
[3, 4]
[4, 1]
[4, 2]
[4, 3]
[4, 4]
這是我實作的邏輯的偽代碼
def backTrack(arr):
if length(arr) == k:
return
loop through from 1 to n <- for i in range(1, n 1):
i = value of loop
add i to an array variable arr <- arr.append(i)
backtrack(arr) <- recurse
remove last index value from arr <- arr = arr[:-1]
對于上面的代碼，我應該得到以下值
on depth 1:
the loop starts with 1
and arr = [1]
then it recuses to depth 2
the loop starts with 1
and arr = [1, 1]
since the length of arr = k =2 it wont recurse further and continue
arr = arr[:-1] = arr = [1]
then i will be 2
and arr = [1,2]
similarly [1, 3] and [1, 4] and then it goes to depth 1 or the parent call
on depth 1
value of i = 1
and arr = 1
now, arr = arr[:-1] that makes arr = []
and now i becomes 2 and the process continues
但是除錯用以下偽代碼撰寫的代碼表明，在深度1上，arr 永遠不會恢復原狀，[1]而是變成[1, 1]了我仍在努力理解為什么會這樣。
以下是帶有列印陳述句的除錯解決方案
class Solution(object):
def combine(self, n, k):
def backTrack(arr, result, depth):
if len(arr) == k:
return
for i in range(1, n 1):
arr.append(i)
print("depth = " str(depth) ", i = " str(i) ", arr=" str(arr))
backTrack(arr, result, depth 1)
print("depth -> " str(depth) ", i-> " str(i) ", arr-> " str(arr))
arr = arr[:-1]
return backTrack([], [], 1)
ob = Solution()
result = ob.combine(4, 2)
下面是除錯后的輸出
depth = 1, i = 1, arr=[1]
depth = 2, i = 1, arr=[1, 1]
depth -> 2, i-> 1, arr-> [1, 1]
depth = 2, i = 2, arr=[1, 2]
depth -> 2, i-> 2, arr-> [1, 2]
depth = 2, i = 3, arr=[1, 3]
depth -> 2, i-> 3, arr-> [1, 3]
depth = 2, i = 4, arr=[1, 4]
depth -> 2, i-> 4, arr-> [1, 4]
depth -> 1, i-> 1, arr-> [1, 1] * going back to parent call arr never becomes 1
depth = 1, i = 2, arr=[1, 2]
depth -> 1, i-> 2, arr-> [1, 2]
depth = 1, i = 3, arr=[1, 3]
depth -> 1, i-> 3, arr-> [1, 3]
depth = 1, i = 4, arr=[1, 4]
depth -> 1, i-> 4, arr-> [1, 4]
我已將除錯器輸出標記*為顯示父呼叫中的 arr 狀態永遠不會恢復原狀1
我想了解為什么會這樣。
uj5u.com熱心網友回復：
arr = arr[:-1]創建一個洗掉最后一個元素的新副本arr并將其分配給區域變數arr。這意味著arr遞回呼叫的其他范圍內的 s 參考了仍然具有最后一個元素的其他串列。
您需要通過撰寫 洗掉此串列中的最后一個元素arr.pop()。
如果您需要進一步解釋 python 中的可變和不可變以及為什么它以這種方式作業，請發表評論。
uj5u.com熱心網友回復：
根據您的偽代碼，實作應該是這樣的：
class Solution(object):
def combine(self, n, k):
total = []
def backTrack(depth, stack):
if depth >= k:
total.append(stack[:])
return
for i in range(1, n 1):
stack.append(i)
backTrack(depth 1, stack)
stack.pop()
backTrack(0, [])
return total
在您的實作中，這行代碼arr = arr[:-1]不會從串列中洗掉任何內容。事實上，它通過使其與最后一個元素相等來阻止整個串列。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/411529.html
標籤：