要返回的结果
异常处理‘
调用helper(找到所有【】开头的子集，放到results里）
递归函数：
递归三要素：
1、递归的定义（接受什么样的参数，返回什么结果，做了什么事情）--找到所有以subset开头的子集，然后丢到results里
2、递归拆解 ---- //deepcopy //reference for()循环，先加，递归，移除
3、递归出口 ----自然而然的return
组合：T（n） = O(答案个数*构造每个答案的时间) = O(n * 2n)
1、题目子集：给定一个含不同整数的集合，返回其所有的子集，
如果 S = [1,2,3]，有如下的解：
[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ] class Solution { /** * @param S: A set of numbers. * @return: A list of lists. All valid subsets. */ public ArrayList<ArrayList<Integer>> subsets(int[] nums) { // write your code here ArrayList<ArrayList<Integer>> results = new ArrayList<>(); //异常处理 if (nums == null || nums.length == 0) { return results; } //排序 Arrays.sort(nums); //调用helper subsetsHelper(nums, 0, new ArrayList<Integer>(), results); //return return results; } //定义helper,注意变量名的意义 private void subsetsHelper(int[] nums, int startIndex, ArrayList<Integer> subsets, ArrayList<ArrayList<Integer>> results) { //deep copy && add to results results.add(new ArrayList<Integer>(subsets)); //递归调用 for (int i = startIndex; i < nums.length; i++) { //添加 subsets.add(nums[i]); subsetsHelper(nums, i + 1, subsets, results); //弹出 subsets.remove(subsets.size() - 1); } } } View Code class Solution { /** * @param S: A set of numbers. * @return: A list of lists. All valid subsets. */ public ArrayList<ArrayList<Integer>> subsets(int[] nums) { //result ArrayList<ArrayList<Integer>> results = new ArrayList<>(); //异常处理 if (nums == null || nums.length == 0) { return results; } //排序 Arrays.sort(nums); //将以{}开头的子集，放入results结果 helper(nums, new ArrayList<Integer>(), results, 0); //返回结果 return results; } //1、定义递归 public void helper(int[] nums, ArrayList<Integer> subset, ArrayList<ArrayList<Integer>> results, int startIndex) { //认为每个子集都是要的结果 //2.递归的拆解 //deepcopy results.add(new ArrayList<Integer>(subset)); for (int i = startIndex; i < nums.length; i++) { subset.add(nums[i]); helper(nums, subset, results, i + 1); subset.remove(subset.size() - 1); } //自然而然返回 //3.return } } View Code
2、permutations（排列）：T（n） = O(n * S) = O（n*n!）,S是所有的答案个数
题目：给定一个数字列表，返回其所有可能的排列。
样例
给出一个列表[1,2,3]，其全排列为：
[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] public class Solution { public List<List<Integer>> permute(int[] nums) { ArrayList<List<Integer>> rst = new ArrayList<List<Integer>>(); if (nums == null) { return rst; } if (nums.length == 0) { rst.add(new ArrayList<Integer>()); return rst; } ArrayList<Integer> list = new ArrayList<Integer>(); helper(rst, list, nums); return rst; } public void helper(ArrayList<List<Integer>> rst, ArrayList<Integer> list, int[] nums){ if(list.size() == nums.length) { rst.add(new ArrayList<Integer>(list)); return; } for(int i = 0; i < nums.length; i++){ if(list.contains(nums[i])){ continue; } list.add(nums[i]); helper(rst, list, nums); list.remove(list.size() - 1); } } } View Code
dfs:从空集出发，不撞墙不回头
从空集出发，先添加第一个，然后第二个....,没有可再加的了，去掉新添加的元素，依次向上返回，.....直到可以向下添加没添加的元素。
bfs:以空集
转载于:https://www.cnblogs.com/lingli-meng/p/6512154.html
