算法通关村-----回溯模板如何解决排列组合问题

组合总和

问题描述

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 对于给定的输入，保证和为 target 的不同组合数少于 150 个。详见leetcode39

问题分析

我们可以从candidates[0]开始，不断选取candidates[0]，直至target-candidates[0]<=0,如果等于0，则我们得到一个满足条件的组合，否则回退一步，去掉一个candidates[0]，添加一个candidates[1]，如此不断进行下去，满足局部枚举➕递归+放下前任，我门可以使用回溯模板来解决。

代码实现

public List<List<Integer>> combinationSum(int[] candidates, int target) {List<Integer> numList = new ArrayList<>();List<List<Integer>> resultList = new ArrayList();combinationSum(candidates,target,0,numList,resultList);return resultList;
}public void combinationSum(int[] candidates, int target,int index,List<Integer> numList,List<List<Integer>> resultList){if(target<0){return;}if(target==0){resultList.add(new ArrayList<>(numList));return;}for(int i=index;i<candidates.length;i++){numList.add(candidates[i]);combinationSum(candidates,target-candidates[i],i,numList,resultList);numList.remove(numList.size()-1);}
}

全排列

问题描述

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

问题分析

排列与组合类似，只是重复元素可以按照不同顺序成为不同的排列，我们不再是按顺序的取，而是定义一个used数组判断给定数组的元素是否被使用。当我们的排列结果中的元素与给定数组个数相同时，即得到一个排列，添加到结果数组中。

代码实现

public List<List<Integer>> permute(int[] nums) {List<List<Integer>> res = new ArrayList<>();LinkedList<Integer> ans = new LinkedList<>();boolean[] used = new boolean[nums.length];permute(res,ans,used,nums);return res;
}
public void permute(List<List<Integer>> res,LinkedList<Integer> ans,boolean[] used,int[] nums){if(ans.size()==nums.length){res.add(new ArrayList<>(ans));return;}for(int i=0;i<nums.length;i++){if(used[i]){continue;}used[i] = true;ans.add(nums[i]);permute(res,ans,used,nums);ans.removeLast();used[i] = false;}
}