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é)果可不可以，流程如下：

1. 給定一個(gè)無(wú)重復(fù)數(shù)組[1,2,3,4,5,7],我們輸入k為3，需要返回所有sum為10的情況。
2. 用回溯法，也就是暴力法，我來(lái)走一遍，首先選擇第一個(gè)數(shù)，數(shù)組[1,2,3,4,5,7]中每一個(gè)數(shù)都可以被選到，如下圖：

image

3. 第二步，我們可以以第一個(gè)數(shù)選擇1為例，第二個(gè)數(shù)就可能選擇[2,3,4,5,7]中的任何一個(gè)數(shù)，如下圖：

image

4. 第三步：選擇第三個(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()
 *   // 撤銷選擇 回到上一步
 * }
 *
 * }
 */

開始解題

1. 初始化變量

var ksum = function(data, k , sum){
    let list = [];
    backtrack(data,list,k,sum)
    return list;
}

function backtrack(data, list, k, sum, tempList = [], start = 0){
}

2. 對(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

3. 終止條件

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é)果里面，而且不管滿不滿足都回到上一步。

4. 書寫完畢，測(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)吧！如果覺得不錯(cuò)的話別忘了點(diǎn)個(gè)贊??再走噢！歡迎把你想到的方法寫在評(píng)論區(qū)喔，作者想要進(jìn)步，哈哈。

個(gè)人博客地址

• 博客地址：小小洋的博客

期待

• 作者大三正在尋找春招實(shí)習(xí)中，期待大佬的青睞~