利用组合模板可以求出集合的所有子集
Subsets
1.对于没有重复数字的数组，代码如下：
class Subsets
{
public void subsets(int[] num)
{
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> path = new ArrayList<>();
Arrays.sort(num);//先按照大小顺序排列
subsetsHelper(res,path,num,0);
System.out.println(res);
}
public void subsetsHelper(ArrayList<ArrayList<Integer>> result,ArrayList<Integer> path,int[] num,int pos)
{
result.add(new ArrayList<Integer>(path));
for (int i = pos; i <num.length;i++)
{
//对于递归的理解，可以采取分层理解，比如数组1，2，3
path.add(num[i]);//把1放进去
subsetsHelper(result,path,num,i+1);//求出含有1的组合
path.remove(path.size()-1);//把1拿出来，回到前面放2，再循环。
}
}
}
subsets.png
[Unique Subsets](http://lintcode.com/problem/unique-
subsets/)
2.对于数组中有重复数字的，只需要在上述代码稍作修改
class Subsets
{
public void subsets(int[] num)
{
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> path = new ArrayList<>();
Arrays.sort(num);//先按照大小顺序排列
subsetsHelper(res,path,num,0);
System.out.println(res);
}
public void subsetsHelper(ArrayList<ArrayList<Integer>> result,ArrayList<Integer> path,int[] num,int pos)
{
result.add(new ArrayList<Integer>(path));
for (int i = pos; i <num.length;i++)
{
//比如1，2，2，3，我们只需要注意只要取一个2，而不用关心取哪个2，我们取首先出现的2，下一个2出现直接跳过，这种组合中只会出现一个2
if (i > 0 && num[i] == num[i-1])
{
continue;
}
//这种会出现两个2的组合
if (i != pos && num[i] == num[i-1])
{
continue;
}
//对于递归的理解，可以采取分层理解，比如数组1，2，3
path.add(num[i]);//把1放进去
subsetsHelper(result,path,num,i+1);//求出含有1的组合
path.remove(path.size()-1);//把1拿出来，回到前面放2，再循环。
}
}
}
排列模板
1.Permutations 全排列
参考程序
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);
}
}
}
2.[Unique Permutations](http://lintcode.com/problem/unique-
permutations/)
参考程序
3.Combinations组合
参考程序
排列组合模板可以应用于以下题目
1.Combination Sum
参考程序 int prev = -1;该变量用于防止出现重复数字的组合
2.Letter Combination of a Phone Number
参考程序每次循环都在不同的字符串中
3.Palindrome Partitioning
参考程序重点关注
4.Restore IP Address
参考程序原理同上
5.Word Break
参考程序
6.Substring with Concatenation of All Words
参考程序
7.N皇后问题
参考答案cols[0]=1表示0行第1列放入一个皇后
