46.排列
给定一个不含重复数字的数组 nums ，返回其所有可能的全排列 。你可以按任意顺序返回答案。
private List<List<Integer>> resList;
public List<List<Integer>> permute(int[] nums) {
if (nums == null || nums.length == 0){
return new ArrayList<>();
}
int n = nums.length;
boolean[] visited = new boolean[n];
resList = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
findByDFS(nums,new ArrayList<Integer>(),visited,i);
}
return resList;
}
private void findByDFS(int[] nums,List<Integer> list,boolean[] visited,int index){
if (visited[index]){
return;
}
list.add(nums[index]);
visited[index] = true;
for (int i = 0; i < nums.length; i++) {
if (!visited[i])
findByDFS(nums,list,visited,i);
}
if (list.size() == nums.length){
resList.add(new ArrayList<>(list));
}
list.remove(list.size()-1);
visited[index] = false;
}
47.含有相同元素求排列
给定一个可包含重复数字的序列 nums ，按任意顺序返回所有不重复的全排列。
private List<List<Integer>> resList;
public List<List<Integer>> permuteUnique(int[] nums) {
if (nums == null || nums.length == 0){
return new ArrayList<>();
}
int n = nums.length;
Arrays.sort(nums);
boolean[] visited = new boolean[n];
resList = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (i != 0 && nums[i] == nums[i-1] && !visited[i-1]){
continue;
}
findByDFS(nums,visited,i,new ArrayList<>());
}
return resList;
}
private void findByDFS(int[] nums,boolean[] visited,int index,List<Integer> list){
if (visited[index]){
return;
}
list.add(nums[index]);
visited[index] = true;
for (int i = 0; i < nums.length; i++) {
if (i != 0 && nums[i] == nums[i-1] && !visited[i-1]){
continue;
}
if (!visited[i])
findByDFS(nums,visited,i,list);
}
if (list.size() == nums.length){
resList.add(new ArrayList<>(list));
}
visited[index] = false;
list.remove(list.size()-1);
}
77.组合
给定两个整数n和k，返回 1 ... n 中所有可能的 k 个数的组合。1...n中的数字只能取一次。
private List<List<Integer>> resList;
public List<List<Integer>> combine(int n, int k) {
if (k == 0){
return new ArrayList<>();
}
resList = new ArrayList<>();
findGroupByDFS(n,new ArrayList<>(),k,1);
return resList;
}
private void findGroupByDFS(int n,List<Integer> list,int k,int start){
if (list.size() == k){
resList.add(new ArrayList<>(list));
return;
}
// (n - (k-list.size())+1)就表示当前的组合序列中的第（list.size() + 1）个数可以从1..n中选取值的范围
for (int i = start; i <= (n - (k-list.size())+1); i++) {
list.add(i);
findGroupByDFS(n,list,k,i+1);
list.remove(list.size()-1);
}
}
39.组合总和
给定一个无重复元素的数组candidates和一个目标数target ，找出candidates中所有可以使数字和为target的组合。
candidates 中的数字可以无限制重复被选取。
说明：
- 所有数字（包括
target）都是正整数。 - 解集不能包含重复的组合。
代码：
private List<List<Integer>> resList;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
if (candidates == null || candidates.length == 0){
return new ArrayList<>();
}
resList = new ArrayList<>();
findCombinationByDFS(candidates,target,new ArrayList<>(),0);
return resList;
}
private void findCombinationByDFS(int[] candidates, int target,List<Integer> list,int index){
if (target == 0){
resList.add(new ArrayList<>(list));
return;
}
for (int i = index; i < candidates.length; i++) {
if (candidates[i] <= target){
list.add(candidates[i]);
findCombinationByDFS(candidates,target-candidates[i],list,i);
list.remove(list.size() - 1);
}
}
}
40.含有相同元素的组合求和
给定一个数组candidates和一个目标数target ，找出candidates中所有可以使数字和为target的组合。
candidates中的每个数字在每个组合中只能使用一次。candidates中可能包含重复元素。
说明：
- 所有数字（包括目标数）都是正整数。
- 解集不能包含重复的组合。
private List<List<Integer>> resList;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
if (candidates == null || candidates.length == 0){
return new ArrayList<>();
}
// 先排序
Arrays.sort(candidates);
int n = candidates.length;
resList = new ArrayList<>();
boolean[] visited = new boolean[n];
findCombinationByDFS(candidates,target,0,new ArrayList<>(),visited);
return resList;
}
private void findCombinationByDFS(int[] candidates,int target,int index,List<Integer> list,boolean[] visited){
if (target == 0){
resList.add(new ArrayList<>(list));
return;
}
for (int i = index; i < candidates.length; i++) {
// 避免重复的元素产生重复的组合
if (i != 0 && candidates[i-1] == candidates[i] && !visited[i-1]){
continue;
}
if (candidates[i] <= target){
visited[i] = true;
list.add(candidates[i]);
findCombinationByDFS(candidates,target-candidates[i],i+1,list,visited);
visited[i] = false;
list.remove(list.size() - 1);
}
}
}
216.组合总和 III
找出所有相加之和为n的k个数的组合。组合中只允许含有1 - 9的正整数，并且每种组合中不存在重复的数字。
说明：
- 所有数字都是正整数。
- 解集不能包含重复的组合。
解析：
组合中不允许重复的数字出现，所以每种数字在一个组合中最多出现一次。
代码：
private List<List<Integer>> resList;
public List<List<Integer>> combinationSum3(int k, int n) {
if (k == 0 || n == 0){
return new ArrayList<>();
}
resList = new ArrayList<>();
findByDFS(k,n,new ArrayList<>(),1);
return resList;
}
private void findByDFS(int k,int n,List<Integer> list,int index){
if (k == 0){
if (n == 0){
resList.add(new ArrayList<>(list));
}
return;
}
for (int i = index; i <= 9; i++) {
list.add(i);
findByDFS(k - 1,n - i,list,i + 1);
list.remove(list.size() - 1);
}
}
78.子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
解析：
这个题其实就是对第77题的一个小扩展，不再是只求某k个数的组合情况，而是求n个数的所有组成0..n个数的组合情况。
private List<List<Integer>> resList;
public List<List<Integer>> subsets(int[] nums) {
if (nums == null || nums.length == 0){
return new ArrayList<>(new ArrayList<>());
}
resList = new ArrayList<>();
// 按照子集合的大小依次寻找所有子集
for (int i = 0; i <= nums.length; i++) {
findSubSets(nums,new ArrayList<>(),i,0);
}
return resList;
}
private void findSubSets(int[] nums,List<Integer> list,int size,int index){
if (list.size() == size){
resList.add(new ArrayList<>(list));
return;
}
for (int i = index; i < nums.length; i++) {
list.add(nums[i]);
findSubSets(nums,list,size,i + 1);
list.remove(list.size() - 1);
}
}
90.含有相同元素求子集
给你一个整数数组nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集不能包含重复的子集。返回的解集中，子集可以按任意顺序排列。
private List<List<Integer>> resList;
public List<List<Integer>> subsetsWithDup(int[] nums) {
if (nums == null || nums.length == 0){
return new ArrayList<>(new ArrayList<>());
}
resList = new ArrayList<>();
Arrays.sort(nums);
boolean[] visited = new boolean[nums.length];
for (int i = 0; i <= nums.length; i++) {
findSubsetByDFS(nums,new ArrayList<>(),i,0,visited);
}
return resList;
}
private void findSubsetByDFS(int[] nums,List<Integer> list,int size,int index,boolean[] visited){
if (size == list.size()){
resList.add(new ArrayList<>(list));
return;
}
for (int i = index; i < nums.length; i++) {
if (i != 0 && nums[i-1] == nums[i] && !visited[i-1]){
continue;
}
list.add(nums[i]);
visited[i] = true;
findSubsetByDFS(nums,list,size,i+1,visited);
visited[i] = false;
list.remove(list.size()-1);
}
}
131.分割字符串
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
private List<List<String>> resList;
public List<List<String>> partition(String s) {
if (s == null || s.length() == 0){
return new ArrayList<>();
}
resList = new ArrayList<>();
findSubStr(s,new ArrayList<>());
return resList;
}
private void findSubStr(String s,List<String> list){
if (s.length() == 0){
resList.add(new ArrayList<>(list));
return;
}
for (int i = 0; i < s.length(); i++) {
if (isPalindrome(s,0,i)){
list.add(s.substring(0,i + 1));
findSubStr(s.substring(i + 1),list);
list.remove(list.size() - 1);
}
}
}
private boolean isPalindrome(String str,int left,int right){
while (left < right){
if (str.charAt(left++) != str.charAt(right--)){
return false;
}
}
return true;
}