一条路往前走，能进则进，不能进则退，换一条路试试，这就是回溯。
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用一次。 说明： 所有数字（包括目标数）都是正整数。 解集不能包含重复的组合。
示例 1: 输入: candidates = [10,1,2,7,6,1,5], target = 8, 所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]
示例 2: 输入: candidates = [2,5,2,1,2], target = 5, 所求解集为: [ [1,2,2], [5] ]
回溯，即 状态重置，一般都是用深度优先搜索。
var combinationSum2 = function(candidates, target){ var len = candidates.length; var result = []; if(len===0) return res; candidates.sort((a,b) => a-b); var arr = []; dfs(candidates,len,0,target,arr,result); return result; } function dfs(candidates,len,begin,rest,arr,result){ if(rest===0){ result.push(arr.slice()); return; } for(var i=begin;i<len;i++){ if(rest-candidates[i]<0) break; if(i>begin && candidates[i]==candidates[i-1]) continue; arr.push(candidates[i]); dfs(candidates,len,i+1,rest-candidates[i],arr,result); arr.pop(); } } var candidates = [10,1,2,7,6,1,5], target = 8; candidates = [2,5,2,1,2], target = 5; candidates = [4,1,1,4,4,4,4,2,3,5],target=10; var res = combinationSum2(candidates,target); console.log(res);
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例: 输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
function permute(nums){ var res = []; var len = nums.length; if(len===0) return res; if(len===1) return [nums]; if(len===2) return [[nums[0],nums[1]],[nums[1],nums[0]]]; const map = new Map(); for(var i=0;i<len;i++){ for(var j=i+1;j<len;j++){ var left = [nums[i],nums[j]]; var right = nums.filter((num,idx) => !(idx==i || idx==j)); var leftRes = permute(left); var rightRes = permute(right); leftRes.forEach(arr1 => { rightRes.forEach(arr2 => { const items = [[...arr1,...arr2],[...arr2,...arr1]]; items.forEach(item => { const key = item.join(); if(!map.has(key)){ map.set(key,item); res.push(item); } }) }) }) } } return res; } var nums =[5,4,6,2]; var res = permute(nums); console.log(res);给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例: 输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ]
function permuteUnique(nums) { var res = []; var len = nums.length; if(len===0) return res; if(len===1) return [nums]; if(len===2) { if(nums[0] === nums[1]){ return [[nums[0],nums[1]]]; }else{ return [[nums[0],nums[1]],[nums[1],nums[0]]]; } } const map = new Map(); for(var i=0;i<len;i++){ for(var j=i+1;j<len;j++){ var left = [nums[i],nums[j]]; var right = nums.filter((num,idx) => !(idx==i || idx==j)); var leftRes = permuteUnique(left); var rightRes = permuteUnique(right); leftRes.forEach(arr1 => { rightRes.forEach(arr2 => { const items = [[...arr1,...arr2],[...arr2,...arr1]]; items.forEach(item => { const key = item.join(); if(!map.has(key)){ map.set(key,item); res.push(item); } }) }) }) } } return res; }; var nums = [1,1,2]; nums = [1,1]; var res = permuteUnique(nums); console.log(res);回溯+Map剪枝
function permuteUnique(nums){ var res = []; var len = nums.length; if(len === 0) return res; nums.sort((a,b) => a-b); var used = []; for(var i=0;i<len;i++){ used[i] = false; } var arr = []; const map = new Map(); dfs(nums,len,0,used,arr,res,map); return res; } function dfs(nums,len,depth,used,arr,res,map){ if(depth === len){ res.push(arr.slice()); return; } for(var i=0;i<len;i++){ if(!used[i]){ arr.push(nums[i]); const key = arr.join(); if(!map.has(key)){ map.set(key,arr); }else{ arr.pop(); continue; } used[i] = true; dfs(nums,len,depth+1,used,arr,res,map); used[i] = false; arr.pop(); } } } var nums = [1,1,3]; nums = [1,1,1,3]; var res = permuteUnique(nums); console.log(res);while(i>0 && nums[i]===nums[i-1] && !used[i-1])实现剪枝。
function permute(nums){ var res = []; var len = nums.length; if(len === 0) return res; nums.sort((a,b) => a-b); var used = []; for(var i=0;i<len;i++){ used[i] = false; } var arr = []; dfs(nums,len,0,used,arr,res); return res; } function dfs(nums,len,depth,used,arr,res){ if(depth === len){ res.push(arr.slice()); return; } for(var i=0;i<len;i++){ if(used[i]) continue; if(i>0 && nums[i]===nums[i-1] && !used[i-1]) continue; used[i] = true; arr.push(nums[i]); dfs(nums,len,depth+1,used,arr,res); used[i] = false; arr.pop(); } } var nums = [1,1,1,3]; // nums=[1,2,3]; var res = permute(nums); console.log(res);