image
一.前言
文章主要給大家分享一個(gè)字節(jié)跳動(dòng)自己出的算法題目--KSUM。作者學(xué)習(xí)了很多，但是沒(méi)有能夠很好的解決這個(gè)問(wèn)題蝙茶，只會(huì)用暴力回溯法解決。如果你有更好的辦法诸老，歡迎評(píng)論區(qū)發(fā)布出來(lái)讓更多人看到隆夯，謝謝啦！
二. 有請(qǐng)主角--KSUM
題目
- 請(qǐng)用算法實(shí)現(xiàn)别伏，從給定的無(wú)序蹄衷、不重復(fù)的數(shù)組
data中，取出K個(gè)數(shù)厘肮，找出K數(shù)之和和與輸入的SUM相等的所有情況愧口，并使算法的時(shí)間/空間復(fù)雜度盡量的低。
var ksum = function(data, k , sum){
}
- 思路
對(duì)于這個(gè)題目作者可以想到的就是回溯法一步一步的嘗試結(jié)果可不可以类茂，流程如下：
- 給定一個(gè)無(wú)重復(fù)數(shù)組
[1,2,3,4,5,7],我們輸入k為3调卑，需要返回所有sum為10的情況抡砂。 - 用回溯法，也就是暴力法恬涧，我來(lái)走一遍注益，首先選擇第一個(gè)數(shù)，數(shù)組
[1,2,3,4,5,7]中每一個(gè)數(shù)都可以被選到溯捆，如下圖：
image
- 第二步丑搔，我們可以以第一個(gè)數(shù)選擇1為例，第二個(gè)數(shù)就可能選擇
[2,3,4,5,7]中的任何一個(gè)數(shù)提揍，如下圖：
image
- 第三步：選擇第三個(gè)數(shù)啤月，這里我們以已經(jīng)選擇1和2為例第三個(gè)數(shù)就只能選擇
[3,4,5,7]，在選擇第三數(shù)的時(shí)候劳跃，我們可以知道選擇7是我們想要的結(jié)果谎仲，返回到結(jié)果的數(shù)組中，并退回上一步去找其他情況刨仑。如果第三步中都沒(méi)有滿足的數(shù)郑诺，也退回第二步去進(jìn)行選擇查找的可能的情況，當(dāng)?shù)诙蕉紱](méi)有符合的情況杉武，就再退回第一步進(jìn)行查找直到所有的情況都遍歷完辙诞，然后返回結(jié)果。
三.書寫代碼
我們以寫js為例
上回溯模板
來(lái)自國(guó)外某大佬轻抱，凡是涉及回溯的都可以使用這個(gè)模板
/**
* backtrack(){
* if(){
* //終止條件
* }
* 枚舉出每一步可選的列表
* for(){
* //做出選擇
* backtrack()
* // 撤銷選擇 回到上一步
* }
*
* }
*/
開(kāi)始解題
- 初始化變量
var ksum = function(data, k , sum){
let list = [];
backtrack(data,list,k,sum)
return list;
}
function backtrack(data, list, k, sum, tempList = [], start = 0){
}
- 對(duì)數(shù)組進(jìn)行遍歷飞涂，選擇
function backtrack(data, list, k, sum, tempList = [], start = 0){
//tempList 已經(jīng)做過(guò)的選擇
//for 枚舉出每一步可選的列表
for(let i = start; i<data.length;i++){
//數(shù)組里面每一項(xiàng)都要選擇
tempList.push(data[i]);
//之后的步驟
backtrack(data, list, k, sum, tempList.slice(0), i+1)
//tempList.slice(0)淺復(fù)制保存一下之前的結(jié)果，以防pop掉祈搜，之后返回空數(shù)組
// 撤銷上一步選擇
tempList.pop();
}
}
首先做出選擇较店，且每一項(xiàng)都會(huì)被選擇，tempList暫存已經(jīng)做的選擇容燕，start初始選擇泽西，且對(duì)起始位置進(jìn)行限制（上一步走到哪里了）,i+1下一步的start
- 終止條件
if(tempList.length === k ){
if(tempList.reduce((a,b) => a+b,0) === sum){
//找到
list.push(tempList);
}
return;//回到上一步
}
終止條件有兩個(gè)，一是選擇的數(shù)已經(jīng)夠了等于k缰趋，二是加起來(lái)的和等于sum捧杉，如果滿足我們將暫存的數(shù)組，push到list結(jié)果里面秘血，而且不管滿不滿足都回到上一步味抖。
- 書寫完畢，測(cè)試
所有代碼如下：
var ksum = function (data, k, sum) {
let list = [];
backtrack(data, list, k, sum)
return list;
}
function backtrack(data, list, k, sum, tempList = [], start = 0) {
if (tempList.length === n) {
if (tempList.reduce((a, b) => a + b, 0) === sum) {
list.push(tempList);
}
return;
}
for (let i = start; i < data.length; i++) {
tempList.push(data[i]);
backtrack(data, list, k, sum, tempList.slice(0), i + 1)
tempList.pop();
}
}
console.log(ksum([1, 2, 3, 4, 5, 6, 7, 8], 3, 10))
結(jié)果：
image
結(jié)果正確灰粮，書寫結(jié)束仔涩，模板真好用！Ｕ持邸熔脂！
結(jié)束
文章看到現(xiàn)在也結(jié)束啦佩研，如果有錯(cuò)誤的話就麻煩大家給我指出來(lái)吧！如果覺(jué)得不錯(cuò)的話別忘了點(diǎn)個(gè)贊??再走噢霞揉！歡迎把你想到的方法寫在評(píng)論區(qū)喔旬薯，作者想要進(jìn)步，哈哈适秩。
個(gè)人博客地址
- 博客地址：小小洋的博客
期待
- 作者大三正在尋找春招實(shí)習(xí)中绊序，期待大佬的青睞~
