@Yano 2019-09-20T10:53:15.000000Z 字数 5462 阅读 4146

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


## 思路

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


## 代码

public List<List<Integer>> permute(int[] nums) {   List<List<Integer>> list = new ArrayList<>();   backtrack(list, new ArrayList<>(), nums);   return list;}private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){   if(tempList.size() == nums.length){      list.add(new ArrayList<>(tempList));   } else{      for(int i = 0; i < nums.length; i++){          if(tempList.contains(nums[i])) continue; // element already exists, skip         tempList.add(nums[i]);         backtrack(list, tempList, nums);         tempList.remove(tempList.size() - 1);      }   }} 

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


## 思路

• 仍然按照上一道题的解法，但是把结果用set保存，最终转换成list。
• 考虑数组中有相同的数，规定必须按照从前到后的顺序使用数字，即数组[1,1]，在组合时，必须先使用第一个1，才能再使用第二个1，这样就避免了结果集重复的情况。

## 代码

public List<List<Integer>> permuteUnique(int[] nums) {    List<List<Integer>> list = new ArrayList<>();    Arrays.sort(nums);    backtrack(list, new ArrayList<>(), nums, new boolean[nums.length]);    return list;}private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, boolean [] used){    if(tempList.size() == nums.length){        list.add(new ArrayList<>(tempList));    } else{        for(int i = 0; i < nums.length; i++){            if(used[i] || i > 0 && nums[i] == nums[i-1] && !used[i - 1]) continue;            used[i] = true;             tempList.add(nums[i]);            backtrack(list, tempList, nums, used);            used[i] = false;             tempList.remove(tempList.size() - 1);        }    }}

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


## 代码

public List<List<Integer>> subsets(int[] nums) {    List<List<Integer>> list = new ArrayList<>();    Arrays.sort(nums);    backtrack(list, new ArrayList<>(), nums, 0);    return list;}private void backtrack(List<List<Integer>> list , List<Integer> tempList, int [] nums, int start){    list.add(new ArrayList<>(tempList));    for(int i = start; i < nums.length; i++){        tempList.add(nums[i]);        backtrack(list, tempList, nums, i + 1);        tempList.remove(tempList.size() - 1);    }}

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


## 代码

public List<List<Integer>> subsetsWithDup(int[] nums) {    List<List<Integer>> list = new ArrayList<>();    Arrays.sort(nums);    backtrack(list, new ArrayList<>(), nums, 0);    return list;}private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int start){    list.add(new ArrayList<>(tempList));    for(int i = start; i < nums.length; i++){        if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates        tempList.add(nums[i]);        backtrack(list, tempList, nums, i + 1);        tempList.remove(tempList.size() - 1);    }} 

# 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是同一个思路，只不过这次不是求子集，而是加上了限制条件：和为指定的值。

## 代码

public List<List<Integer>> combinationSum(int[] nums, int target) {    List<List<Integer>> list = new ArrayList<>();    Arrays.sort(nums);    backtrack(list, new ArrayList<>(), nums, target, 0);    return list;}private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){    if(remain < 0) return;    else if(remain == 0) list.add(new ArrayList<>(tempList));    else{         for(int i = start; i < nums.length; i++){            tempList.add(nums[i]);            backtrack(list, tempList, nums, remain - nums[i], i); // not i + 1 because we can reuse same elements            tempList.remove(tempList.size() - 1);        }    }}

# 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


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


## 代码

public List<List<Integer>> combinationSum2(int[] nums, int target) {    List<List<Integer>> list = new ArrayList<>();    Arrays.sort(nums);    backtrack(list, new ArrayList<>(), nums, target, 0);    return list;}private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){    if(remain < 0) return;    else if(remain == 0) list.add(new ArrayList<>(tempList));    else{        for(int i = start; i < nums.length; i++){            if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates            tempList.add(nums[i]);            backtrack(list, tempList, nums, remain - nums[i], i + 1);            tempList.remove(tempList.size() - 1);         }    }} 

• 私有
• 公开
• 删除