首页 > 代码库 > 第一节.排列组合
第一节.排列组合
总结：什么时候用回溯法?
如果题目要求求出所有满足条件的解，一般来说是用回溯法，记住回溯法的模板，对不同的题目只需要修改这个条件即可。
回溯法的本质是在问题的解空间树上做深度优先搜索（DFS）。这节课主要讲了四个排列组合的问题，分别是子集，带重复元素的子集，全排列，带重复元素的全排列。本文分析求子集的问题，给出程序模板。
题目：给定一个含不同整数的集合，返回其所有的子集。
样例：
如果 S = [1,2,3]，有如下的解：
[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], []]
代码：
public class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> results = new ArrayList<List<Integer>>(); helper(nums,results,new ArrayList<Integer>(),0); return results; } public void helper(int[] nums,List<List<Integer>> res,List<Integer> cur,int start){ List<Integer> subset = new ArrayList<Integer>(cur); res.add(subset); for(int i=start;i<=nums.length-1;i++){ cur.add(nums[i]); helper(nums,res,cur,i+1); cur.remove(cur.size()-1); } }}
写的时候要注意递归的三要素：
1.递归的定义。这里的helper函数定义为：将所有以当前cur子集开头的所有子集（包含当前cur）加入到结果res中。
2.递归的出口。即满足什么条件保存答案。这里对每个遍历得到的cur都保存答案。
3.递归的拆解。拆解为更小规模的问题。
注意理解这里的DFS思想:当前cur开头的所有子集找完了，才去找下一个cur开头的所有子集。
第一节.排列组合
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。