關(guān)于我的 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.
候選數(shù)字無(wú)重復(fù)。
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.
候選數(shù)字有重復(fù)叙量。
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);
// 避免重復(fù)元素出現(xiàn)
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 {
// 遞歸，從下一個(gè)元素開始
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.
候選數(shù)字無(wú)重復(fù)九串，但是每個(gè)數(shù)字可以出現(xiàn)多次绞佩。
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開始猪钮，因?yàn)樵乜梢灾貜?fù)出現(xiàn)多次
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.
候選數(shù)字有重復(fù)品山，但是每個(gè)數(shù)字只能出現(xiàn)一次。
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++) {
// 跳過(guò)重復(fù)的元素
if(i > startIdx && candidates[i] == candidates[i-1]) {
continue;
}
path.add(candidates[i]);
// 遞歸烤低，從i + 1開始肘交，因?yàn)樵刂荒艹霈F(xiàn)一次
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.
候選數(shù)字無(wú)重復(fù)。
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.
候選數(shù)字有重復(fù)扑馁。
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++) {
// 跳過(guò)重復(fù)的元素
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);
}
}
}
