回溯可以看作是蛮力法的升级版。它在求解问题的每一步都尝试所有可能的方案，最终找到所有可行的方案。回溯非常适合解决由多个步骤组成的问题，每个步骤都有多个选项。在某个步骤选择了其中一个选项后，就会进入下一步，然后就会面临新的选项。以这种方式重复选择，直到达到最终状态。由于回溯法是对所有选项组成的树进行深度优先遍历，如果求解问题的步骤很多或者每一步都面临多个选项，那么遍历整棵树会花费更多的时间。如果明确有些子树是不需要遍历的，那么在遍历的时候就应该避开这些子树，以优化效率。使用回溯时避免遍历不必要的子树的方法通常称为剪枝。集合的组合与排列从包含m个元素的集合中选出n个（0≤n≤m）元素组成一个子集。子集也可以称为组合。如果两个子集（组合）的元素完全相同但顺序不同，则可以认为它们是相同的子集（组合）。从包含m个元素的集合中选择n个元素（0≤n≤m）并按某种顺序形成排列。m等于n的排列也称为完全排列。如果两个排列的元素完全相同但顺序不同，则两个排列是两个不同的排列。也就是说，排列与元素的顺序有关，这与组合不同。所有子集输入一个没有重复数字的数据集，请找出它的所有子集。例如，数据集[1,2]有4个子集，分别是[]、[1]、[2]和[1,2]。varhelper=function(nums,index,subset,result){if(index==nums.length){result.push(subset.slice());//子集需要深拷贝}elseif(index{if(cur===nums.length){ans.推（t。切片（））；返回;}t.push(nums[cur]);dfs(cur+1,nums);t.pop(t.length-1);dfs(cur+1,nums);};dfs（0，数字）；返回答案；}；具有k个元素的组合给定两个整数n和k，返回1...n中k个数字的所有可能组合。varhelper=function(nums,index,subset,result,k){if(index==nums.length&&subset.length==k){result.push(subset.slice());//子集应该是深拷贝}elseif(index0&&index0&&indexa-b);助手（候选人，0，[]，结果，目标）；返回结果;};排列给定一个没有重复数字的集合，找到它的所有排列。比如集合[1,2,3]有6个全排列，分别是[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2]和[3,2,1]。我不明白varswap=function(nums,i,j){if(i!==j){lettemp=nums[i];nums[i]=nums[j];nums[j]=温度；}};varhelper=function(nums,i,result){if(i==nums.length){结果。推（nums.slice（））;}else{for(letj=i;j0){helper(left-1,right,parenthesis+"(",result);}if(left0&&segI<3){helper(s,i+1,segI+1,""+ch,ip+seg+".,结果)}}};/***@param{string}s*@return{string[]}*/varrestoreIpAddresses=function(s){letresult=[];助手（s，0，0，“”，“”，结果）；返回结果;};典型的面试题。如果解决一个问题需要几个步骤，并且每一步都面临多个选项，你可以尝试用回溯法解决问题。回溯法所应用的问题的一个特点是问题有多种解法，题目往往要求列出所有的解法。
