回溯算法团灭排列/组合/子集问题

预计阅读时间：7 分钟今天就来聊三道考察频率高，而且容易让人搞混的算法问题，分别是求子集（subset），求排列（permutation），求组合（combination）。这几个问题都可以用回溯算法解决。一、子集问题很简单，输入一个不包含重复数字的数组，要求算法输出这些数字的所有子集。vectorvectorint>> subsets(vectorint>& nums);比如输入 nums = [1,2,3]，你的算法应输出 8 个子集，包含空集和本身，顺序可以不同：[ [],[1],[2],[3],[1,3],[2,3],[1,2],[1,2,3] ]第一个解法是利用数学归纳的思想：假设我现在知道了规模更小的子问题的结果，如何推导出当前问题的结果呢？具体来说就是，现在让你求 [1,2,3] 的子集，如果你知道了 [1,2] 的子集，是否可以推导出 [1,2,3] 的子集呢？先把  [1,2] 的子集写出 ………………………………