组合

[编程题]组合

热度指数：11852 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给出两个整数n和k，返回从1到n中取k个数字的所有可能的组合

例如：

如果n=4，k=2，结果为

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

示例1

输入

2,1

输出

[[1],[2]]

示例2

输入

3,1

输出

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

算法知识视频讲解

Java

科学xx

import java.util.*;

public class Solution {
/**
*
* @param n int整型
* @param k int整型
* @return int整型ArrayList<ArrayList<>>
*/
private ArrayList<ArrayList<Integer>> res = new ArrayList<>();
public ArrayList<ArrayList<Integer>> combine (int n, int k) {
if (n <=0 || k <= 0){
return new ArrayList<>();
}
//从1开始
backTrack(1,n,k,new ArrayList<>());
return res;
}

public void backTrack(int start,int n, int k, ArrayList<Integer> list){
if (list.size() == k){
res.add(new ArrayList<>(list));
}else {
for (int i = start; i <= n ; i++) {
list.add(i);
//递归寻找下一个值，从i+1开始
backTrack(i+1,n,k,list);
//回溯
list.remove(list.size() - 1);
}
}
}
}

编辑于 2020-09-15 19:27:40 回复(0)

Java

whynotybb

public ArrayList<ArrayList<Integer>> combine(int n, int k) {
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    ArrayList<Integer> list = new ArrayList<>();
    core(res, list, n, k); return res;
}
//回溯法 private void core(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> list, int n, int k) { if (list.size() == k) {
        ArrayList<Integer> temp=new ArrayList<>(list);
        res.add(temp);
    } else { for (int i = 1; i <= n; i++) {
            //只有当前i大于上一个被选入的，并且i没有被选入时才入选，负责会出现2,1；1,2 if (list.isEmpty()||(!list.contains(i)&&list.get(list.size()-1)<i)) {
                list.add(i);
                core(res, list, n, k);
                list.remove(list.size() - 1);
            }
        }
    }
}

发表于 2019-08-06 16:41:21 回复(0)

Java

卖萌の哈士奇

//每次取一个数，分两种情况，组合中存在该数和组合中不存在该数，然后在两种情况下继续向下递归
import java.util.ArrayList;
import java.util.List;
public class Solution {
    private ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    
    public ArrayList<ArrayList<Integer>> combine(int n, int k) {
        if(n < k || k <= 0){
            return res;
        }
        List<Integer> numList = new ArrayList<>();
        for(int i = 1; i <= n; i++){
            numList.add(i);
        }
        ArrayList<Integer> list = new ArrayList<>();
        dfs(n,k,numList,list);
        return res;
    }
    
    private void dfs(int n, int k,List<Integer> numList ,ArrayList<Integer> list){
        if(k == 0){
            res.add(new ArrayList<>(list));
            return;
        }
        if(n < k || k < 0 || n <= 0 || numList.size() == 0){
            return;
        }
        int num = numList.remove(0);
        list.add(num);
        dfs(n-1,k-1,numList,list);
        list.remove(list.size() - 1);
        dfs(n-1,k,numList,list);

        numList.add(0,num);

    }
}

发表于 2019-03-15 01:24:00 回复(0)

Java

美团内推码WncroPl

public class Solution {
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> combine(int n, int k) {
        getAllCombineList(1, n, k, new ArrayList<>());
        return res;
    }

    public void getAllCombineList(int start, int n, int k, ArrayList<Integer> list) {
        if(k == 0) {
            res.add(new ArrayList<>(list)); // 如果仅仅add(list)那么list.remove后,这个res也会减少 

            return;
        }

        for (int i = start; i <= n; i++) {
            list.add(i);
            getAllCombineList(i + 1, n, k - 1, list);
            list.remove(list.size() - 1);
        }

    }
}

发表于 2018-04-03 10:18:06 回复(0)

Java

PG.13

//回溯法。
import java.util.*;
public class Solution {
ArrayList<ArrayList<Integer>>res = new ArrayList<ArrayList<Integer>>();
public ArrayList<ArrayList<Integer>> combine(int n, int k) {
ArrayList<Integer>list = new ArrayList<Integer>();
backTrace(1,list,n,k);
return res;
}
public void backTrace(int index,ArrayList<Integer>list,int n,int k){
if(list.size()>=k){
res.add(new ArrayList<Integer>(list));
return;
}
for(int i=index;i<=n;i++){
list.add(i);
backTrace(i+1,list,n,k);
list.remove(list.size()-1);
}
}
}

发表于 2017-10-30 11:32:42 回复(0)

Java

城市里的养猫者

 public static List<List<Integer>> combine(int n, int k) { List<List<Integer>> combs = new ArrayList<List<Integer>>();
		combine(combs, new ArrayList<Integer>(), 1, n, k); return combs;
	} public static void combine(List<List<Integer>> combs, List<Integer> comb, int start, int n, int k) { if(k==0) {
			combs.add(new ArrayList<Integer>(comb)); return;
		} for(int i=start;i<=n;i++) {
			comb.add(i);
			combine(combs, comb, i+1, n, k-1);
			comb.remove(comb.size()-1);
		}
	}