[关闭]
@Yano 2019-09-20T10:53:15.000000Z 字数 5462 阅读 4209

LeetCode 排列组合 题目汇总

LeetCode


公众号

coding 笔记、点滴记录,以后的文章也会同步到公众号(Coding Insight)中,希望大家关注^_^

https://github.com/LjyYano/Thinking_in_Java_MindMapping

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]
]

思路

对于nums数组中的每一个数,都依次放入结果集中,如果结果集中已经包含这个数,就继续下一次循环。

以数组[1,2,3]为例,每次循环的结果是:

[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]

代码

  1. public List<List<Integer>> permute(int[] nums) {
  2. List<List<Integer>> list = new ArrayList<>();
  3. backtrack(list, new ArrayList<>(), nums);
  4. return list;
  5. }
  6. private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){
  7. if(tempList.size() == nums.length){
  8. list.add(new ArrayList<>(tempList));
  9. } else{
  10. for(int i = 0; i < nums.length; i++){
  11. if(tempList.contains(nums[i])) continue; // element already exists, skip
  12. tempList.add(nums[i]);
  13. backtrack(list, tempList, nums);
  14. tempList.remove(tempList.size() - 1);
  15. }
  16. }
  17. }

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]
]

思路

这道题比上一道题多了一个条件,即数组中有重复的数。有两种思路:

代码

  1. public List<List<Integer>> permuteUnique(int[] nums) {
  2. List<List<Integer>> list = new ArrayList<>();
  3. Arrays.sort(nums);
  4. backtrack(list, new ArrayList<>(), nums, new boolean[nums.length]);
  5. return list;
  6. }
  7. private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, boolean [] used){
  8. if(tempList.size() == nums.length){
  9. list.add(new ArrayList<>(tempList));
  10. } else{
  11. for(int i = 0; i < nums.length; i++){
  12. if(used[i] || i > 0 && nums[i] == nums[i-1] && !used[i - 1]) continue;
  13. used[i] = true;
  14. tempList.add(nums[i]);
  15. backtrack(list, tempList, nums, used);
  16. used[i] = false;
  17. tempList.remove(tempList.size() - 1);
  18. }
  19. }
  20. }

78. Subsets

Given a set of distinct integers, nums, return all possible subsets.

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],
  []
]

思路

与题目Permutations类似,但是Permutations是达到数组长度才将结果保存,而本题目是求子集,任何集合都需要保存。其中for循环的条件也稍微有些变化。

代码

  1. public List<List<Integer>> subsets(int[] nums) {
  2. List<List<Integer>> list = new ArrayList<>();
  3. Arrays.sort(nums);
  4. backtrack(list, new ArrayList<>(), nums, 0);
  5. return list;
  6. }
  7. private void backtrack(List<List<Integer>> list , List<Integer> tempList, int [] nums, int start){
  8. list.add(new ArrayList<>(tempList));
  9. for(int i = start; i < nums.length; i++){
  10. tempList.add(nums[i]);
  11. backtrack(list, tempList, nums, i + 1);
  12. tempList.remove(tempList.size() - 1);
  13. }
  14. }

90. Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

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],
  []
]

思路

处理重复的数,和上面是一个思路,即只允许用前面的数字。

代码

  1. public List<List<Integer>> subsetsWithDup(int[] nums) {
  2. List<List<Integer>> list = new ArrayList<>();
  3. Arrays.sort(nums);
  4. backtrack(list, new ArrayList<>(), nums, 0);
  5. return list;
  6. }
  7. private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int start){
  8. list.add(new ArrayList<>(tempList));
  9. for(int i = start; i < nums.length; i++){
  10. if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates
  11. tempList.add(nums[i]);
  12. backtrack(list, tempList, nums, i + 1);
  13. tempList.remove(tempList.size() - 1);
  14. }
  15. }

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]
]

思路

Subsets是同一个思路,只不过这次不是求子集,而是加上了限制条件:和为指定的值。

代码

  1. public List<List<Integer>> combinationSum(int[] nums, int target) {
  2. List<List<Integer>> list = new ArrayList<>();
  3. Arrays.sort(nums);
  4. backtrack(list, new ArrayList<>(), nums, target, 0);
  5. return list;
  6. }
  7. private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
  8. if(remain < 0) return;
  9. else if(remain == 0) list.add(new ArrayList<>(tempList));
  10. else{
  11. for(int i = start; i < nums.length; i++){
  12. tempList.add(nums[i]);
  13. backtrack(list, tempList, nums, remain - nums[i], i); // not i + 1 because we can reuse same elements
  14. tempList.remove(tempList.size() - 1);
  15. }
  16. }
  17. }

40. Combination Sum II (can't reuse same element)

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]
]

思路

和上一题有两点不同的地方:

解决数组中可能有重复的数字:

if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates

解决不能重复利用数组中的数字(上一题中最后是i,而不是i + 1):

backtrack(list, tempList, nums, remain - nums[i], i + 1);

代码

  1. public List<List<Integer>> combinationSum2(int[] nums, int target) {
  2. List<List<Integer>> list = new ArrayList<>();
  3. Arrays.sort(nums);
  4. backtrack(list, new ArrayList<>(), nums, target, 0);
  5. return list;
  6. }
  7. private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
  8. if(remain < 0) return;
  9. else if(remain == 0) list.add(new ArrayList<>(tempList));
  10. else{
  11. for(int i = start; i < nums.length; i++){
  12. if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates
  13. tempList.add(nums[i]);
  14. backtrack(list, tempList, nums, remain - nums[i], i + 1);
  15. tempList.remove(tempList.size() - 1);
  16. }
  17. }
  18. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注