【原】最近刚跟一个年薪80万的总监聊天，他说：职场上晋升的核心从来都不是能力，而是老板的信任，而大多数人都搞错了。。。

数据结构和算法 2024-03-15 发布于上海

展开全文

最近一网友说自己跟一个年薪80万的总监聊天，总监提了很多掏心窝子的建议，其中一个就是：职场上晋升的核心从来都不是能力而是老板的信任。你有多大的信任就能调动多大的资源？而绝大多数人搞错了以为我有能力了，自然而然就获得了老板的信任。任何人都需要被认同和支持，老板也是人也需要你的情绪价值。

对于这种看法我不是很认同，我觉得信任都是建立在能力的基础上的，如果一个人没有能力，很难产生信任，但也不乏一些拍马溜须，阿谀奉承之徒。大多数情况下我们还是要提高自己的能力，但也要和领导搞好关系。只有能力和信任都具有才是职场中晋升的核心，我们再来看下各位网友的看法。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第77题：组合，我们来看下。

问题描述

来源：LeetCode第77题

难度：中等

给定两个整数 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

问题分析

这题返回 1 到 n 中所有 k 个数的组合，我们知道排列是有顺序的，但组合是没有顺序的，比如[1,2]和[2,1]只能算一个组合。组合选择的过程我们可以把它看作是一棵树，如下图所示：

因为每个数字在每个组合中只能选择一次，所以当选择当前数字的时候，下一步只能选择他后面的数字，当选择个数达到 k 个的时候就不要再往下选了，然后把这个组合添加到最终的集合中。

JAVA：

public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> ans = new ArrayList<>();
    dfs(ans, new ArrayList<>(k), n, k, 1);
    return ans;
}

private void dfs(List<List<Integer>> ans, List<Integer> path, int n, int k, int start) {
    if (path.size() == k) {
        ans.add(new ArrayList<>(path));
        return;
    }
    for (int i = start; i <= n; i++) {
        path.add(i);// 选择
        dfs(ans, path, n, k, i + 1);// 递归到下一层
        path.remove(path.size() - 1);// 撤销选择
    }
}

C++：

public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ans;
        vector<int> path;
        dfs(ans, path, n, k, 1);
        return ans;
    }

    void dfs(vector<vector<int>> &ans, vector<int> &path, int n, int k, int start) {
        if (path.size() == k) {
            ans.push_back(path);
            return;
        }
        for (int i = start; i <= n; i++) {
            path.push_back(i);// 选择
            dfs(ans, path, n, k, i + 1);// 递归到下一层
            path.pop_back();// 撤销选择
        }
    }

C：

void dfs(int **ans, int *path, int size, int n, int k, int start, int *returnSize, int *returnColumnSizes) {
    if (size == k) {
        ans[*returnSize] = (int *) malloc(sizeof(int) * size);
        memcpy(ans[*returnSize], path, size * sizeof(int));
        returnColumnSizes[*returnSize] = k;
        (*returnSize)++;
        return;
    }
    for (int i = start; i <= n; i++) {
        path[size++] = i;// 选择
        dfs(ans, path, size, n, k, i + 1, returnSize, returnColumnSizes);// 递归到下一层
        size--;// 撤销选择
    }
}

int **combine(int n, int k, int *returnSize, int **returnColumnSizes) {
    int **ans = (int **) malloc(sizeof(int *) * 1000000);
    int *path = (int *) malloc(sizeof(int) * k);
    *returnSize = 0;
    *returnColumnSizes = (int *) malloc(sizeof(int) * 1000000);
    dfs(ans, path, 0, n, k, 1, returnSize, *returnColumnSizes);
    return ans;
}

Python：

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

    def dfs(start: int):
        if len(path) == k:
            ans.append(path[:])
            return
        for i in range(start, n + 1):
            path.append(i)  # 选择
            dfs(i + 1)  # 递归到下一层
            path.pop()  # 撤销选择

    dfs(1)
    return ans