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

回溯算法本质上就是暴力穷举，优化一下叫剪枝。难点在于理解递归树和撤销选择。

一、全排列

publicList<List<Integer>>permute(int[]nums){List<List<Integer>>result=newArrayList<>();backtrack(nums,newboolean[nums.length],newArrayList<>(),result);returnresult;}privatevoidbacktrack(int[]nums,boolean[]used,List<Integer>path,List<List<Integer>>result){if(path.size()==nums.length){result.add(newArrayList<>(path));return;}for(inti=0;i<nums.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;}}

二、组合

publicList<List<Integer>>combine(intn,intk){List<List<Integer>>result=newArrayList<>();backtrack(n,k,1,newArrayList<>(),result);returnresult;}privatevoidbacktrack(intn,intk,intstart,List<Integer>path,List<List<Integer>>result){if(path.size()==k){result.add(newArrayList<>(path));return;}for(inti=start;i<=n;i++){path.add(i);backtrack(n,k,i+1,path,result);path.remove(path.size()-1);}}

三、子集

publicList<List<Integer>>subsets(int[]nums){List<List<Integer>>result=newArrayList<>();backtrack(nums,0,newArrayList<>(),result);returnresult;}privatevoidbacktrack(int[]nums,intstart,List<Integer>path,List<List<Integer>>result){result.add(newArrayList<>(path));for(inti=start;i<nums.length;i++){path.add(nums[i]);backtrack(nums,i+1,path,result);path.remove(path.size()-1);}}

💡 觉得有用的话，点赞 + 关注【张老师技术栈】吧！