组合问题算法优化之去重复的思考

上次的加法问题，抽象之后，是一个组合求和问题，算是一个算法题目。但是对于算法中的去重复部分，还有一些疑惑。

算法

def combination_sum(candidates, target):
    result = []
    def backtrack(path, start, current_sum):
        if current_sum == target:
            result.append(path.copy())
            return
        if current_sum > target:
            return  # 剪枝
        for i in range(start, len(candidates)):
            # 选择当前元素
            path.append(candidates[i])
            backtrack(path, i, current_sum + candidates[i])  # 允许重复选择，start仍为i
            # 回溯
            path.pop()
    backtrack([], 0, 0)
    return result

def find_combination(target, scores):
    stack = [(target, [], 0)]
    attempt_count = 0
    while stack:
        current_target, current_combination, start_index = stack.pop()
        attempt_count += 1
        # 检查是否找到满足条件的组合
        if current_target == 0 and len(current_combination) < 15:
            return current_combination
        # 检查是否需要剪枝
        if current_target < 0 or len(current_combination) >= 15:
            continue
        # 尝试所有可能的分数选择
        for i in range(start_index, len(scores)):
            new_target = current_target - scores[i]
            new_combination = current_combination + [scores[i]]
            stack.append((new_target, new_combination, i))
    return None

根据介绍，算法使用的是一个回溯算法。

使用的是深度优先搜索，不断往下进行计算，计算完成或失败后，返回，回溯，继续搜索下一个节点。

初步的想法是，对于一个组合[k0,k1,k2...kn]，每次都搜一遍[k0,k1,...kn]，这样就可以搜索全部都结果。

那么为什么要传入一个i参数，也就是range里面的start_index参数，跳过组合中该位置的参数前面的参数的搜索？

根据提示的样例，说是为了避免重复，如假设目标和是6，参数组合是[3,2,1]，那么搜索结果可能有[3,2,1]，也有[3,1,2],而这个i参数，就是避免这样的重复搜索。

那么原理是什么呢？

抽象一下，就是在列m之后，再搜索第m+1列时，为什么第m列为kp时，第m+1列不用搜索第k1,k2,...k[p-1]，这些内容？

思考

我们来归纳一下： 在m列进行k0搜索时，会搜索m+1列的k0,k1,...kp,...kn,这些内容。 因为是深度优先搜索，所以会把m列k0之后所有内容搜索完。 之后会进行m列k1搜索，这个时候，是否还要搜索m+1列的k0，不必了，因为在前面的组合中，已经搜索了这样的组合[...k0,k1,...]。 如果这个时候再进行[...k1,k0,...]这个组合的话，其实是重复的。（因为求解的是组合，不需要考虑顺序。） 所以，此时只需要搜索m+1列的k1,...kp,...kn这些内容。

当我们进行m列kp搜索时，是否还需要搜索[...kp,k[p-1]...]这样的的组合，不需要了，因为在进行m列k[p-1]搜索时，已经进行过m+1列的kp的搜索，因为p-1< p . 同样的，也不需要进行[...kp,ki...] ，i < p这样的搜索了，因为在进行m列ki的搜索时，也搜索了m+1列的kp了，因此i < p。

所以，在进行第m列kp搜索时，第m+1列，只需要搜索kp...kn，记第位置p这里的元素，在进行第m+1轮搜索时，只需要从第位置p这里开始进行搜索。

如果我们画一个矩阵的话，可以看到连线是水平或者向下的方向，而没有往上的方向。