leetcode【39,40,77,78,90,216】排列组合问题

组合问题&＃xff1a;

题目中涉及到all  possible sulutions时就要用到搜索算法&＃xff0c;用深度优先搜索来解决。

leetcode 78.Subsets

题目描述

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums &＃61; [1,2,3]
Output:
[[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[]
]

思路&＃xff1a;

用递归的思想&＃xff0c;从空集合开始&＃xff0c;找到以nums中每个元素开始的所有可能的组合数。

实现&＃xff1a;

public List> subsets(int[] nums) {//recursion:程序的一种实现方式&＃xff0c;函数自己调用自己List> ret&＃61;new ArrayList<>();if(nums&＃61;&＃61;null){return ret;}ArrayList sub&＃61;new ArrayList<>();//将所有以空集开头的集合加入到ret中helper(ret,sub,nums,0);return ret;
}
//递归的三要素之一&＃xff1a;定义
//将以subset开头的所有的子集全部找到&＃xff0c;并加入到ret中
private void helper(List> ret,ArrayList sub,int[] nums,int fromIndex){//递归的三要素之二&＃xff1a;极限小的状态//if(XXX){ return }//每当进入到一次新的递归&＃xff0c;相等于从一个点进入到新的点&＃xff0c;都需要将sub的结果加入到ret//referenceret.add(new ArrayList<>(sub));//递归三要素之三&＃xff1a;如何变为更小的状态for(int i&＃61;fromIndex;i}

leetcode 90. Subsets II

题目描述&＃xff1a;

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: [1,2,2]
Output:
[[2],[1],[1,2,2],[2,2],[1,2],[]
]

思路&＃xff1a;

和上面求集合的方法是一样的&＃xff0c;只不过因为数组中包含重复的元素&＃xff0c;所以在求组合数时&＃xff0c;需要对重复的元素进行过滤。所以我们在逐个寻找以nums中某个元素开始的所有集合时&＃xff0c;都判断一下当前元素是否和上一个元素一样&＃xff0c;如果一样&＃xff0c;就跳过。

实现&＃xff1a;

public List> subsetsWithDup(int[] nums) {List> ret&＃61;new ArrayList<>();if(nums&＃61;&＃61;null||nums.length&＃61;&＃61;0) return ret;Arrays.sort(nums);ArrayList sub&＃61;new ArrayList<>();fun(nums,ret,sub,0);return ret;
}
private void fun(int[] nums,List> ret,ArrayList sub,int fromIndex){ret.add(new ArrayList<>(sub));for(int i&＃61;fromIndex;i}

leetcode 77. Combinations

题目描述&＃xff1a;

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

Example:

Input: n &＃61; 4, k &＃61; 2
Output:
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]

思路&＃xff1a;

要求给出all possible combnations,所以我们也需要使用搜索算法来实现。可选的元素是1-n,每次选择一个元素后&＃xff0c;都需要使用搜索算法&＃xff08;递归&＃xff09;将它与后面的元素做组合&＃xff0c;集合中元素个数为k时停止搜索&＃xff08;递归截止的条件&＃xff09;。

因为我们的集合中必须存在k个元素&＃xff0c;所以在从第一个元素开始逐个加入集合时&＃xff0c;我们最多只能加到第n-k&＃43;1个元素&＃xff0c;这样才保证集合中存在K个元素&＃xff0c;比如加入[1,2,3,4,5,6,7,8,9,10],k&＃61;5,那我们集合开头的元素最多是6开头&＃xff0c;这样保证集合至少有5个元素&＃xff0c;[6,7,8,9,10]&＃xff0c;若我们选择7&＃xff0c;则此时剩下的元素就不够5个了。

实现&＃xff1a;

public List> combine(int n, int k) {List> ret&＃61;new ArrayList<>();ArrayList sub&＃61;new ArrayList<>();if(k>n||k<0||n<0){return ret;}fun(n,k,1,ret,sub);return ret;
}
private void fun(int n,int k,int indexFrom,List> ret, ArrayList sub){if(k&＃61;&＃61;0){ret.add(new ArrayList<>(sub));//basecase,子集满了return;}for(int i&＃61;indexFrom;i<&＃61;n-k&＃43;1;i&＃43;&＃43;){sub.add(i);//选择一个数fun(n,k-1,i&＃43;1,ret,sub);//递归搜索sub.remove(sub.size()-1);//不选择这个数}
}

其他题目&＃xff1a;

https://blog.csdn.net/orangefly0214/article/details/89959891