專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

最近螞蟻集團發(fā)布全員信，宣布對薪酬體系進行重大調整！目的是要提升員工薪酬收入的流動性和激勵即時性，進一步優(yōu)化激勵機制。

17級及以下同學，13薪沒有了，并入到每月的基本工資中發(fā)放，員工每個月拿到手的錢會更多，增加月度現金流。此項調整自2025年1月生效，并于2025年3月底發(fā)薪開始體現，并補齊1月、2月差額。

18級及以上同學，13薪并入到年終獎，與績效激勵掛鉤。自2025年績效年度起，基于年度考核增加1個月的月薪作為獎金基數，提高整體薪酬中浮動的占比。我的理解是如果績效不好的話，是不是13薪也沒了？

如果是在職的還好說，13薪并入到基本工資的時候，基本工資相當于漲了一下，對于以后入職的是不是意味著沒有13薪了？

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

來看下今天的算法題，這題是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 個數的組合，所謂的組合也就是從數組中選擇 k 個數，這種選擇只是其中的一個組合。我們知道排列是有順序的，但組合是沒有順序的，比如[1,2]和[2,1]只能算一個組合。組合選擇的過程我們可以把它看作是一棵樹，如下圖所示：

因為每個數字在每個組合中只能選擇一次，所以選擇當前數字的時候，下一步只能選擇他后面的數字，否則就會出現類似于[1,2]和[2,1]這種重復的組合。當選擇個數達到 k 個的時候就不要再往下選了，然后把這個組合添加到最終的集合中，這是一道回溯算法問題，代碼非常簡單。

JAVA：

public List > combine( int n, int k) {     List > ans =  new ArrayList<>();     dfs(ans, new ArrayList<>(k), n, k, 1);     return ans; } private void dfs(List > ans, List 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

 > combine(int n, int k) {         vector

 > ans;         vector

 path;         dfs(ans, path, n, k, 1);         return ans;     }     void dfs(vector

 > &ans, vector

 &path, int n, int k, int start) {         if (path.size() == k) {             ans.emplace_back(path);             return;         }         for (int i = start; i <= n; i++) {             path.emplace_back(i);// 選擇             dfs(ans, path, n, k, i + 1);// 遞歸到下一層             path.pop_back();// 撤銷選擇         }     }

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

筆者簡介

博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。