算法面试——回溯算法：全排列、组合、子集

回溯算法本质上就是暴力穷举优化一下叫剪枝。难点在于理解递归树和撤销选择。一、全排列publicListListIntegerpermute(int[]nums){ListListIntegerresultnewArrayList();backtrack(nums,newboolean[nums.length],newArrayList(),result);returnresult;}privatevoidbacktrack(int[]nums,boolean[]used,ListIntegerpath,ListListIntegerresult){if(path.size()nums.length){result.add(newArrayList(path));return;}for(inti0;inums.length;i){if(used[i])continue;used[i]true;path.add(nums[i]);backtrack(nums,used,path,result);path.remove(path.size()-1);used[i]false;}}二、组合publicListListIntegercombine(intn,intk){ListListIntegerresultnewArrayList();backtrack(n,k,1,newArrayList(),result);returnresult;}privatevoidbacktrack(intn,intk,intstart,ListIntegerpath,ListListIntegerresult){if(path.size()k){result.add(newArrayList(path));return;}for(intistart;in;i){path.add(i);backtrack(n,k,i1,path,result);path.remove(path.size()-1);}}三、子集publicListListIntegersubsets(int[]nums){ListListIntegerresultnewArrayList();backtrack(nums,0,newArrayList(),result);returnresult;}privatevoidbacktrack(int[]nums,intstart,ListIntegerpath,ListListIntegerresult){result.add(newArrayList(path));for(intistart;inums.length;i){path.add(nums[i]);backtrack(nums,i1,path,result);path.remove(path.size()-1);}} 觉得有用的话点赞 关注【张老师技术栈】吧