AlgoPressAppearance
0077-组合
https://leetcode.cn/problems/combinations
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。
示例 1：
输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
示例 2：
输入：n = 1, k = 1
输出：[[1]]
提示：
- 1 <= n <= 20
- 1 <= k <= n
思路排列去重
组合问题，回溯法，每次添加一个数字，然后递归到下一层，直到满足k的长度后加入结果。 注意组合时前面已经出现过的数字不需要再次出现，所以 backtrack 的时候， i+1
参考代码
csharp
public class Solution{
private List<IList<int>> result = new List<IList<int>>();
private List<int> CopyList(List<int> input){
List<int> list = new List<int>();
for(int i=0; i<input.Count; i++){
list.Add(input[i]);
}
return list;
}
private void backtrack(int cur, int n, int k, List<int> list){
if(k == 0){
//输出
result.Add(CopyList(list));
return;
}
for(int i = cur; i<=n; i++){
if(!list.Contains(i)){
//Console.WriteLine("Add i={0}",i);
list.Add(i);
backtrack(i+1,n,k-1,list);
//Console.WriteLine("Remove i={0}",i);
list.Remove(i);
}
}
}
public IList<IList<int>> Combine(int n, int k) {
List<int> list = new List<int>();
backtrack(1,n,k,list);
return result;
}
}
思路组合【官方】
参考代码
csharp
public class Solution {
private List<IList<int>> result = new List<IList<int>>();
private List<int> CopyList(List<int> input){
List<int> list = new List<int>();
for(int i=0; i<input.Count; i++){
list.Add(input[i]);
}
return list;
}
private void backtrack(int cur, int n, int k, List<int> list){
if(list.Count + (n - cur +1) < k){
return;
}
if(list.Count == k){
result.Add(CopyList(list));
return;
}
//选择当前位置
list.Add(cur);
backtrack(cur+1,n,k,list);
list.Remove(cur);
//不选当前位置
backtrack(cur+1,n,k,list);
}
public IList<IList<int>> Combine(int n, int k) {
List<int> list = new List<int>();
backtrack(1,n,k,list);
return result;
}
}
复习:20220512 注意组合有start
组合的时候不分顺序，比如1,2 和 2,1 是一样的，所以我们就排序好数据，从前往后。 当前面的数据处理完之后，比如是 i , 那么下一个开始的数字就是 i+1 ， 这样保证再次遍历到前面的数据
csharp
public class Solution {
List<IList<int>> result = new List<IList<int>>();
private void dfs(int n,int start, int k, List<int> list){
if(k == 0){ //结束
result.Add(new List<int>(list.ToArray()));
}
for(int i=start; i<=n; i++){
if(!list.Contains(i)){
list.Add(i);
dfs(n,i+1,k-1,list);
list.RemoveAt(list.Count-1);
}
}
}
public IList<IList<int>> Combine(int n, int k) {
List<int> list = new List<int>();
dfs(n,1,k,list);
return result;
}
}
csharp
public class Solution {
List<IList<int>> result = new List<IList<int>>();
private void dfs(int n,int start, int k, List<int> list){
if(k == 0){ //结束
result.Add(new List<int>(list.ToArray()));
return;
}
if(start > n){
return;
}
//选择这个数据
list.Add(start);
dfs(n,start+1,k-1,list);
list.RemoveAt(list.Count-1);
//不选这个数据
dfs(n,start+1,k,list);
}
public IList<IList<int>> Combine(int n, int k) {
List<int> list = new List<int>();
dfs(n,1,k,list);
return result;
}
}
复习:20220617
csharp
public class Solution {
IList<IList<int>> result = new List<IList<int>>();
private void dfs(int n, int k, int begin, List<int> list){
if(k == 0){
//输出
result.Add(new List<int>(list.ToArray()));
}
for(int i=begin; i<=n; i++){
list.Add(i);
dfs(n,k-1,i+1,list);
list.RemoveAt(list.Count-1);
}
}
public IList<IList<int>> Combine(int n, int k) {
List<int> list = new List<int>();
dfs(n,k,1,list);
return result;
}
}