פתרון שילוב של סכום Leetcode  


רמת קושי בינוני
נשאל לעתים קרובות Adobe Airbnb אמזון בעברית תפוח עץ Atlassian בלומברג Byte eBay פייסבוק גולדמן זאקס Google לינקדין מיקרוסופט אורקל Snapchat בצורת ריבוע סופר VMware מעבדות וולמארט
אלגוריתמים מערך חזרה לאחור קידוד ראיון אישי הוכחת ראיונות LeetCode LeetCodeSolutions

הבעיה שילוב סכום Leetcode פתרון מספק לנו מערך או רשימת מספרים שלמים ויעד. נאמר לנו למצוא את השילובים שניתן ליצור בעזרת מספרים שלמים אלה בכל מספר פעמים שמסתכמים ביעד הנתון. באופן רשמי יותר, אנו יכולים להשתמש במספרים השלמים הנתונים בכל מספר פעמים שהם מוסיפים ליעד הנתון. הפלט הנדרש הוא הצירופים שיש להם את הסכום השווה ליעד הנתון.

דוגמהפתרון שילוב של סכום Leetcode  

candidates = [2,3,6,7], target = 7
[[2,2,3],[7]]

הסבר: התפוקה הנתונה מסכמת את היעד הנתון. גם אם ננסה להמציא כל שילוב אחר. בסופו של דבר נסדר את אותם מספרים שלמים בסדר אחר. אבל הסדר לא משנה רק הצירופים כן.

candidates = [2,3,5], target = 8
[[2,2,2,2],[2,3,3],[3,5]]

הסבר: מכיוון שנוכל להשתמש באותו מספר שלם בכל מספר פעמים. בפלט השתמשנו פעמיים פעמים בפלט הראשון. באופן דומה, בפלט השני חוזר 2. אנו יכולים לוודא שכל 2 התפוקות מסתכמות ביעד הנתון.

גישה לפתרון שילוב של סכום Leetcode  

הגישה לבעיה פשוטה למצוא. באופן כללי, בבעיות כאלה אנו נדרשים להשתמש במעקב אחורה. מכיוון שבשאלות כאלה אנו נדרשים לבצע חיפוש מלא ולמצוא את התשובה. אז ראשית, אנו ממיינים את רשימת המספרים השלמים שניתנים לנו. לאחר מכן, אנו יוצרים פונקציה רקורסיבית הממשיכה להוסיף מספר שלם לרשימת המספרים השלמים הזמניים הנוכחית ולעקוב אחר הסכום הנותר שנדרש להוספת יעד נתון. אז בתוך הפונקציה הרקורסיבית, אנו שומרים על שני מקרי בסיס. המקרה הבסיסי הראשון הוא לבדוק אם הסכום הנותר שנדרש יהיה שלילי. במקרה כזה, נשוב מהפונקציה הרקורסיבית. מקרה הבסיס השני הוא מצבנו הנדרש אם הסכום הנותר שווה לאפס. אם הסכום הנותר הוא אפס פירוש הדבר שהגענו ליעד הנדרש שלנו. בשלב זה, אנו דוחפים את הרשימה הזמנית הנוכחית של מספרים שלמים למערך הפלט של המערכים.

ראה גם
בעיית שינוי מטבע

קופונים  

קוד C ++ לפתרון שילוב של סכום Leetcode

#include <bits/stdc++.h>
using namespace std;

void backtrack(vector<vector<int>> &output, vector<int> &current, vector<int> &candidates, int remain, int start){
    if(remain < 0)
        return;
    else if(remain == 0)output.push_back(current);
    else {
        for(int i=start;i<candidates.size();i++){
            current.push_back(candidates[i]);
            backtrack(output, current, candidates, remain - candidates[i], i);
            current.pop_back();
        }
    }
}

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> output;
    vector<int> current;
    sort(candidates.begin(), candidates.end());
    backtrack(output, current, candidates, target, 0);
    return output;
}

int main(){
  vector<int> cand = {2, 3, 6, 7};
  vector<vector<int>> output = combinationSum(cand, 7)	;
  for(auto x: output){
    for(auto y: x)
      cout<<y<<" ";
    cout<<endl;
  }
}
2 2 3 
7

קוד Java לפתרון Combination Sum Leetcode

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static List<List<Integer>> combinationSum(int[] nums, int target) {
      List<List<Integer>> list = new ArrayList<>();
      Arrays.sort(nums);
      backtrack(list, new ArrayList<>(), nums, target, 0);
      return list;
  }
  
  private static void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
      if(remain < 0) return;
      else if(remain == 0) list.add(new ArrayList<>(tempList));
      else{ 
          for(int i = start; i < nums.length; i++){
              tempList.add(nums[i]);
              backtrack(list, tempList, nums, remain - nums[i], i); // not i + 1 because we can reuse same elements
              tempList.remove(tempList.size() - 1);
          }
      }
  }

  public static void main (String[] args) throws java.lang.Exception
  {
    int[] nums = {2, 3, 6, 7};
    List<List<Integer>> output = combinationSum(nums, 7);
    for(List<Integer> x: output){
      for(Integer y: x)
        System.out.print(y+" ");
      System.out.println();
    }
  }
}
2 2 3
7

ניתוח מורכבות  

מורכבות זמן

O (N ^ (M / T + 1)) כאשר N הוא מספר המועמדים, M הוא המועמד הקטן ביותר מבין כל המספרים השלמים הנתונים, ו- T הוא ערך היעד. לפיכך מורכבות הזמן היא אקספוננציאלית וזה צפוי מכיוון שהאלגוריתם הוא מעקב חוזר רקורסיבי.

מורכבות בחלל

O (T / M), כאשר T הוא ערך היעד ו- M הוא האלמנט המינימלי בקרב כל המועמדים האחרים.