LeetCode关于子集合 SubSet，排列 Permutat
关于我的 Leetcode 题目解答，代码前往 Github：https://github.com/chenxiangcyr/leetcode-answers
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.
候选数字无重复。
For example,
If nums = [1,2,3], a solution is:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
class Solution {
public List<List<Integer>> subsets = new ArrayList<List<Integer>>();
public List<Integer> subset = new ArrayList<Integer>();
public List<List<Integer>> subsets(int[] nums) {
travel(nums, 0);
subsets.add(new ArrayList<Integer>());
return subsets;
}
public void travel(int[] nums, int startIdx) {
for(int i = startIdx; i < nums.length; i++) {
subset.add(nums[i]);
subsets.add(new ArrayList(subset));
if(i + 1 < nums.length) {
travel(nums, i + 1);
}
// backtracking
subset.remove(subset.size() - 1);
}
}
}
LeetCode题目：90. Subsets II
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.
候选数字有重复。
For example,
If nums = [1,2,2], a solution is:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
class Solution {
public List<List<Integer>> subsets = new ArrayList<List<Integer>>();
public List<Integer> subset = new ArrayList<Integer>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
// 排序
Arrays.sort(nums);
travel(nums, 0);
subsets.add(new ArrayList<Integer>());
return subsets;
}
public void travel(int[] nums, int startIdx) {
for(int i = startIdx; i < nums.length; i++) {
subset.add(nums[i]);
subsets.add(new ArrayList(subset));
if(i + 1 < nums.length) {
travel(nums, i + 1);
}
// backtracking
subset.remove(subset.size() - 1);
// 避免重复元素出现
while(i + 1 < nums.length && nums[i + 1] == nums[i]) {
i++;
}
}
}
}
LeetCode题目：77. Combinations
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
For example,
If n = 4 and k = 2, a solution is:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
class Solution {
private List<List<Integer>> result = new ArrayList<List<Integer>>();
private List<Integer> path = new ArrayList<Integer>();
public List<List<Integer>> combine(int n, int k) {
travel(n, k, 1);
return result;
}
public void travel(int n, int k, int start) {
if(start > n) {
return;
}
for(int i = start; i <= n; i++) {
path.add(i);
if(path.size() == k) {
result.add(new ArrayList<>(path));
}
else {
// 递归，从下一个元素开始
travel(n, k, i + 1);
}
// backtracking
path.remove(path.size() - 1);
}
}
}
LeetCode题目：39. Combination Sum
Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
候选数字无重复，但是每个数字可以出现多次。
Note:
- All numbers (including target) will be positive integers.
- The solution set must not contain duplicate combinations.
For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:
[
[7],
[2, 2, 3]
]
class Solution {
private List<List<Integer>> result = new ArrayList<List<Integer>>();
private List<Integer> path = new ArrayList<Integer>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
travel(candidates, target, 0);
return result;
}
public void travel(int[] candidates, int target, int startIdx) {
if(target < 0) {
return;
}
else if(target == 0) {
result.add(new ArrayList<>(path));
}
else {
for(int i = startIdx; i < candidates.length; i++) {
path.add(candidates[i]);
// 递归，依旧从i开始，因为元素可以重复出现多次
travel(candidates, target - candidates[i], i);
// backtracking
path.remove(path.size() - 1);
}
}
}
}
LeetCode题目：40. Combination Sum II
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
候选数字有重复，但是每个数字只能出现一次。
Note:
- All numbers (including target) will be positive integers.
- The solution set must not contain duplicate combinations.
For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
class Solution {
private List<List<Integer>> result = new ArrayList<List<Integer>>();
private List<Integer> path = new ArrayList<Integer>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
travel(candidates, target, 0);
return result;
}
public void travel(int[] candidates, int target, int startIdx) {
if(target < 0) {
return;
}
else if(target == 0) {
result.add(new ArrayList<>(path));
}
else {
for(int i = startIdx; i < candidates.length; i++) {
// 跳过重复的元素
if(i > startIdx && candidates[i] == candidates[i-1]) {
continue;
}
path.add(candidates[i]);
// 递归，从i + 1开始，因为元素只能出现一次
travel(candidates, target - candidates[i], i + 1);
// backtracking
path.remove(path.size() - 1);
}
}
}
}
LeetCode题目：46. Permutations
Given a collection of distinct numbers, return all possible permutations.
候选数字无重复。
For example,
[1,2,3] have the following permutations:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
class Solution {
public List<List<Integer>> permutations = new ArrayList<List<Integer>>();
public List<Integer> permutation = new ArrayList<Integer>();
public List<List<Integer>> permute(int[] nums) {
travel(nums);
return permutations;
}
public void travel(int[] nums) {
for(int i = 0; i < nums.length; i++) {
if(!permutation.contains(nums[i])) {
permutation.add(nums[i]);
// arrive the last digit
if(permutation.size() == nums.length) {
permutations.add(new ArrayList(permutation));
} else {
travel(nums);
}
// backtracking
permutation.remove(permutation.size() - 1);
}
}
}
}
LeetCode题目：47. Permutations II
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
候选数字有重复。
For example,
[1,1,2] have the following unique permutations:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
class Solution {
public List<List<Integer>> permutations = new ArrayList<List<Integer>>();
public List<Integer> permutation = new ArrayList<Integer>();
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
travel(nums, new boolean[nums.length]);
return permutations;
}
public void travel(int[] nums, boolean [] visited) {
for(int i = 0; i < nums.length; i++) {
// 跳过重复的元素
if(visited[i] || (i > 0 && nums[i] == nums[i-1] && !visited[i - 1])) {
continue;
}
visited[i] = true;
permutation.add(nums[i]);
// arrive the last digit
if(permutation.size() == nums.length) {
permutations.add(new ArrayList(permutation));
} else {
travel(nums, visited);
}
// backtracking
visited[i] = false;
permutation.remove(permutation.size() - 1);
}
}
}
