目录
1. 全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
class Solution {
public List<List<Integer>> permute(int[] nums) {
int m = nums.length;
List<List<Integer>> list = new ArrayList();
List<Integer> tmp = new ArrayList();
dfs(nums,0,nums.length-1,tmp,list);
return list;
}
public static void dfs(int[] nums,int start,int end,List<Integer> tmp,List<List<Integer>> list){
if(start > end){
for(int i = 0;i <=end;i++){
tmp.add(nums[i]);
}
list.add(new ArrayList(tmp));
tmp.clear();
return;
}
for(int i = start;i <=end;i++){
{int temp = nums[i]; nums[i] =nums[start];nums[start] = temp;}
dfs(nums,start+1,end,tmp,list);
{int temp = nums[i]; nums[i] =nums[start];nums[start] = temp;}
}
}
}
2. 全排列 II
给定一个可包含重复数字的序列?nums?，按任意顺序?返回所有不重复的全排列。
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
int m = nums.length;
List<List<Integer>> list = new ArrayList();
List<Integer> tmp = new ArrayList();
dfs(nums,0,nums.length-1,tmp,list);
return list;
}
public static void dfs(int[] nums,int start,int end,List<Integer> tmp,List<List<Integer>> list){
if(start > end){
for(int i = 0;i <=end;i++){
tmp.add(nums[i]);
}
list.add(new ArrayList(tmp));
tmp.clear();
return;
}
Set<Integer> set = new HashSet();
for(int i = start;i <=end;i++){
if(!set.contains(nums[i])){
set.add(nums[i]);
{int temp = nums[i]; nums[i] =nums[start];nums[start] = temp;}
dfs(nums,start+1,end,tmp,list);
{int temp = nums[i]; nums[i] =nums[start];nums[start] = temp;}
}
}
}
}
3. 组合
给定两个整数?n?和?k，返回范围?[1, n]?中所有可能的?k?个数的组合。
你可以按?任何顺序?返回答案。
class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> result = new ArrayList();
Deque<Integer> deque = new ArrayDeque();
dfs(n,1,k,deque,result);
return result;
}
public void dfs(int n,int index, int k,Deque deque,List<List<Integer>> result){
if(k == 0){
result.add(new ArrayList(deque));
return;
}
for(int i = index;i <= n-k+1;i++){
deque.addLast(i);
dfs(n,i+1,k-1,deque,result);
deque.removeLast();
}
}
}
4. 子集
给你一个整数数组?nums?，数组中的元素?互不相同?。返回该数组所有可能的子集（幂集）。
解集?不能?包含重复的子集。你可以按?任意顺序?返回解集。
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList();
Deque<Integer> deque = new ArrayDeque();
int m = nums.length;
result.add(new ArrayList());
dfs(nums,m,0,result,deque);
return result;
}
public void dfs(int[] nums,int m, int index,List<List<Integer>> result,Deque<Integer> deque){
if(index == m){
return ;
}
for(int i = index;i < m ; i++){
deque.addLast(nums[i]);
result.add(new ArrayList(deque));
dfs(nums,m,i+1,result,deque);
deque.removeLast();
}
}
}
5. 子集 II
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList();
Deque<Integer> deque = new ArrayDeque();
int m = nums.length;
result.add(new ArrayList());
dfs(nums,m,0,result,deque);
return result;
}
public void dfs(int[] nums,int m, int index,List<List<Integer>> result,Deque<Integer> deque){
if(index == m){
return ;
}
for(int i = index;i < m ; i++){
if(i > index && nums[i] == nums[i-1]){
continue;
}
deque.addLast(nums[i]);
result.add(new ArrayList(deque));
dfs(nums,m,i+1,result,deque);
deque.removeLast();
}
}
}
