我正在尝试解决LeetCode上的第377题:组合总和 IV问题。
题目示例:
输出:7
解释:
可能的组合方式有:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
以下是目前为止我给出的解决方案:
class Solution(object):
def combinationSum4(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
result = []
def dfs(i, curr, total):
# 打印当前搜索层级
# print(i)
if total == target:
# 当总和等于目标值时,将当前组合添加至结果列表
result.append(curr[:])
return
if total > target or i >= len(nums):
# 若总和大于目标值或已经搜索完数组,则返回
return
# 选择当前数字,进入下一层递归
curr.append(nums[i])
dfs(i, curr, total + nums[i])
# 回溯,撤销当前选择
curr.pop()
# 不选择当前数字,进入下一层递归
dfs(i + 1, curr, total)
dfs(0, [], 0)
print(result)
# 返回组合总数
return len(result)
该解决方案目前只能产生(1,1,2)、(1,2,1)或(2,1,1)中的一种解,以及(1,3)或(3,1)中的一种解,而不能完全生成所有解。我不确定如何构造递归树以生成所有可能的解决方案。通常来说,对于不同的解决方案,比如不重复组合(只包含上述可能解中的一种)、不重复序列等情况,应该如何思考构建递归树的方法呢?非常感谢任何帮助!