[LeetCode]LCR 081. 组合总和

题目

思路

先找出数组中最小元素，与目标数比较：

        若目标数小，则无组合可能；

        若相等，则输出该最小元素；

        若目标数大，则寻找一元素的组合可能，寻找二元素的组合可能

以candidates = [2,3,6,7], target = 7为例：

2<7，找一元素组合可能：7

          找两元素组合可能：2+5的组合数，3+4的组合数，6+1的组合数      

                                        7的组合可能：7，2+2+3，2+3+2，3+2+2

                找5的组合数：2<5                                                        5的组合可能：2+3，3+2

                                找一元素组合可能：[ ]

                                找二元素组合可能：2+3的组合数，3+2的组合数

                                        找3的组合数：2<3                                3的组合可能：3

                                                 找一元素组合可能：3

                                                 找二元素组合可能：2+1的组合数

                                                         找1的组合数：2>1                              

                                        找2的组合数：2=2                                 2的组合可能：2                

                找4的组合数：2<4                                                         4的组合可能：2+2

                                找一元素组合可能：[ ]

                                找二元素组合可能：2+2的组合数

                                         找2的组合数：2=2                                2的组合可能：2

                找1的组合数：2>1                                                         1的组合可能：[ ]

完全没办法排除加法的交换律...

官方思路：回溯+剪枝

知识补充

回溯的本质是穷举；【算法】回溯算法_codecapture的博客-CSDN博客

常用来解决：

        组合问题：N个数里面按一定规则找出k个数的集合

        切割问题：一个字符串按一定规则有几种切割方式

        子集问题：N个数的集合里有多少符合条件的子集

        排列问题：N个数按一定规则全排列的排列方式个数

        棋盘问题：N皇后，解数独等等

概括的说就是能解决抽象为N叉树的各种问题，方法是在集合中递归查找子集，其中集合的大小等于树的宽度，递归的次数等于树的深度；

 

回溯算法的模板为：
 
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }
 
    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

比较参考博客里和上面描述的推导过程，发现是在找两元素组合可能时出错，导致同一组合重复出现；所以在确定两元素组合中的某一元素后，应该对组合数的集合范围进行修改；

再次推导：以candidates = [2,3,6,7], target = 7为例：

2<7，找一元素组合可能：7

          找两元素组合可能：2+5的组合数[2,3,6,7]，3+4的组合数[3,6,7]，6+1的组合数 [6,7]    

                                                                                                         7的组合可能：7，2+2+3

                找5的组合数[2,3,6,7]：2<5                                               5的组合可能：2+3

                                找一元素组合可能：[ ]

                                找二元素组合可能：2+3的组合数[2,3,6,7]，3+2的组合数[3,6,7]

                                        找3的组合数[2,3,6,7]：2<3                       3的组合可能：3

                                                 找一元素组合可能：3

                                                 找二元素组合可能：2+1的组合数[2,3,6,7]

                                                         找1的组合数[2,3,6,7]：2>1                              

                                        找2的组合数[3,6,7]：3>2                          2的组合可能：[ ]            

                找4的组合数[3,6,7]：3<4                                                  4的组合可能：[ ]

                                找一元素组合可能：[ ]

                                找二元素组合可能：3+1的组合数[3,6,7]

                                         找1的组合数：3>1                                   1的组合可能：[ ]

                找1的组合数 [6,7]：6>1                                                    1的组合可能：[ ]

解题过程

//是错误的代码
def backtracking(candidates, num, out, index):    
//candidates待选列表  num目标值  out输出列表  index第几层，用于控制到根节点时切换保存列表
    if min(candidates) > num:
        out.pop()
    elif min(candidates) == num:
        out.append(min(candidates))
    else:
        for i in range(len(candidates)):
            new = candidates[i:]
            new_v = num - candidates[i]
            if new_v < 0:
                break
            elif new_v == 0:
                out.append(candidates[i])
                break
            else:
                index = index + 1
                out.append(candidates[i])
                backtracking(new, new_v, out, index)
    index -= 1
 
    if index == 1:
        total_out.append(out)
        out *= 0
 
    return

题解中的办法

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        # 回溯，无重复元素，根据剩余值凑成目标
        ans = []
        path = []
        candidates.sort() # 预先排序，
        # 收集逻辑为target == 0
 
        def backtracking(index,path,target):
            if index >= len(candidates) or target < 0:
                return 
            if target == 0: # 收集条件
                ans.append(path[:])
                return    
            for i in range(index,len(candidates)):  # 注意可以重复收集          
                path.append(candidates[i])  # 做选择
                backtracking(i,path,target-candidates[i])
                path.pop() # 取消选择
         
        backtracking(0,[],target)
        return ans
 
作者：菜狗阿笨-暂告一段落
链接：https://leetcode.cn/problems/Ygoe9J/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

总结

按照再次推导的思路写代码时发现，因为多层循环的嵌套和多个判别条件导致不会对结果进行保存和删除，只能一遍遍调试；

调试了得有一两个小时，发现变量作用域和我以为的不一样，即用等号赋值的操作会被解释成创建一个局部变量；

局部变量	全局变量
“index = index - 1”	“index -= 1”
out=[ ]	out *=0

以及在2-3-[3,6,7]k=2和3-3-[3,6,7]k=1时需要pop的次数不同，因为2-3-[3,6,7]k=2的另一分叉数上存在2-2-3的父节点2；

题解中的办法就是标准的回溯模板，需要学习，不要自己造各种判断条件！！！