我要招人

去企业版

首页 > 试题广场 >

组合

[编程题]组合

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

给定两个正整数 n 和 k ，请你返回 [1,n] 中所有包含 k 个数的组合。

你可以按任意顺序返回结果。

数据范围： $1 \le k \le n \le 20 \$

示例1

输入

3,2

输出

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

算法知识视频讲解

唐氏综合征

这道题是一个经典的递归回溯算法,

1. 按照循环一次尝试每一个元素，纳入列表，直到列表元素个数满足条件

2. 需要注意的是，该题要求元素前后位置不可以颠倒，即 [2,3] 合法，[3, 2]非法，因此不需要每次都从头开始遍历，也不需要使用额外的记忆化数组来加速求解

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @param k int整型
     * @return int整型ArrayList<ArrayList<>>
     */
    public static ArrayList<ArrayList<Integer>> combine(int n, int k) {
        // write code here
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        dfs(n, k, 0, res, new ArrayList<>());
        return res;
    }


    public static void dfs(int n, int k, int pos, ArrayList<ArrayList<Integer>> res, ArrayList<Integer> current) {
        // 找到了满足的一组
            if (current.size() == k){
                res.add(new ArrayList<>(current)); return;
            }

        for (int i = pos; i < n; i++) {
            current.add(i + 1); // i+1 表示第 i个元素的值
            dfs(n, k, i + 1, res, current);
            current.remove(current.size() - 1);
        }
    }
}

发表于 2024-05-17 09:44:50 回复(0)

Python3

揪住小洋

class Solution:

def com(self,begin,end,k):

res = []

if k==0:

return res

elif k==1:

for i in range(begin,end):

res.append([i])

else:

for i in range(begin,end):

cur = [i]

for m in self.com(i+1,end,k-1):

res.append(cur+m)

return res

def combine(self , n: int, k: int) -> List[List[int]]:

return self.com(1,n+1,k)

发表于 2024-05-04 19:35:30 回复(0)

TypeScript

牛客343123665号

export function combine(n: number, k: number) {

// write code here

const temp = [];

const twoArr = [];

function backStack(n, k, startI) {

if (temp.length === k) {

twoArr.push(temp);

// 这一行里直接将组合数组加进组合集合数组中，得不到对应的数据。需要写成 twoArr.push(temp.slice), 才行。谁能解释下吗？

return;

}

for(let i=startI; i<=n; i++) {

temp.push(i);

backStack(n, k, i+1);

temp.pop()

}

backStack(n, k, 1)

return twoArr

}

发表于 2024-04-14 00:38:10 回复(0)

小谷围做题家

package main
//import "fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @param k int整型 
 * @return int整型二维数组
*/
func combine( n int ,  k int ) [][]int {
    ans:=[][]int{}
    var dfs func([]int,int)
    dfs=func(path []int,idx int){
        if len(path)==k{
            tmp:=make([]int,k)
            copy(tmp,path)
            ans=append(ans,tmp)
            return
        }
        for i:=idx;i<=n;i++{
            path=append(path,i)
            dfs(path,i+1)
            path=path[:len(path)-1]
        }
    }
    dfs([]int{},1)
    return ans
}

发表于 2023-03-15 17:35:42 回复(0)

努力学好算法的小白

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param k int整型 
     * @return int整型ArrayList<ArrayList<>>
     */
    static ArrayList<ArrayList<Integer>> result = new ArrayList<>();
    static ArrayList<Integer> path = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> combine (int n, int k) {
        // write code here
        backtrading(n,k,1);
        return result;

    }

    public static void backtrading(int n,int k ,int startIndex){
        //递归结束条件
        if(path.size() == k){
            result.add(new ArrayList<>(path));
            return;
        }

        //for嵌套
        for(int i = startIndex;i<= n- (k-path.size())+1;i++  ){
            path.add(i);
            backtrading(n,k,i+1);
            //回溯
            path.remove(path.size()-1);
        }

    }
}

发表于 2022-10-23 08:54:24 回复(0)

Python2

菜鸡升职记

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param n int整型
# @param k int整型
# @return int整型二维数组
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/7cfd3675cc964ae6818a771ac97ece5f?tpId=196&tqId=40448&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title=
    算法：
        题目要求统计从区间[1,n]中选取k个数的所有组合，我们变换下思维，也就是从1 ~ n这n种物品选取k种放入k个盒子中的所有组合。使用辅助数组visited标记元素是否已访问。
        设dfs(idx, combine)，idx表示当前访问的盒子下标，combine表示当前已放置元素组合
        初始化：
            dfs(0, [])
        dfs(idx, combine):
            若idx = k：找到一组解并记录，return
            枚举可以放入idx的元素：
                加入combine，继续递归；
                回溯
    复杂度：
        时间复杂度：O(n * (n - 1) * ... * (n - k + 1) / (k * (k - 1) * ... * 1)) # 排列组合数
        空间复杂度：O(k)
    """

    def combine(self, n, k):
        # write code here
        def dfs(idx, combine):
            if idx == k:
                res.append(combine[:])
                return

            for i in range(1, n + 1):
                if not visited[i]:
                    if combine and combine[-1] > i:
                        continue
                    combine.append(i)
                    visited[i] = True
                    dfs(idx + 1, combine)
                    combine.pop()
                    visited[i] = False

        res, visited = [], [False] * (n + 1)

        dfs(0, [])

        return res


if __name__ == "__main__":
    sol = Solution()

    n, k = 3, 2

    res = sol.combine(n, k)

    print res

发表于 2022-06-26 07:35:02 回复(0)

Java

世界杯2009

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) {
        // write code here
        dfs(n, k, new ArrayList<>(), 1);
        return res;
    }

    private void dfs(int n, int k, ArrayList<Integer> one, int start) {
        // 退出条件，找到了目标组合
        if (one.size() == k) {
            res.add(new ArrayList<>(one));
            return;
        }
        for (int i = start; i <= n; i++) {
            // 选择当前数
            one.add(i);
            dfs(n, k, one, i + 1);
            // 回退
            one.remove(one.size() - 1);
        }
    }
}

发表于 2022-04-16 16:09:01 回复(0)