الجمع بين حل Leetcode  


مستوى الصعوبة متوسط
كثيرا ما يطلب في أدوبي Airbnb أمازون أجهزة آبل Atlassian بلومبرغ ByteDance يباي Facebook جولدمان ساكس جوجل لينكد إن: Microsoft أوراكل Snapchat مربع اوبر في إم وير مختبرات وول مارت
خوارزميات مجموعة التراجع الترميز المقابلة الشخصية مقابلة LeetCode LeetCodeSolutions

توفر لنا مجموعة حل Sum 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. يمكننا التحقق من أن جميع النواتج الثلاثة تصل إلى الهدف المحدد.

نهج الجمع بين حل Leetcode  

نهج المشكلة سهل العثور عليه. بشكل عام ، في مثل هذه المشاكل ، نحن مطالبون باستخدام التراجع. لأنه في مثل هذه الأسئلة ، يُطلب منا إجراء بحث كامل والعثور على الإجابة. أولًا ، نقوم بفرز قائمة الأعداد الصحيحة المعطاة لنا. بعد ذلك ، نقوم بإنشاء دالة تكرارية تحافظ على إضافة عدد صحيح إلى القائمة المؤقتة الحالية للأعداد الصحيحة وتتبع المجموع المتبقي المطلوب لجمع ما يصل إلى الهدف المحدد. إذن ، داخل الدالة العودية ، نحتفظ بحالتين أساسيتين. الحالة الأساسية الأولى هي التحقق مما إذا كان المجموع المتبقي المطلوب سالبًا. في هذه الحالة ، سنعود من الدالة العودية. الحالة الأساسية الثانية هي الشرط المطلوب إذا كان المجموع المتبقي يساوي صفرًا. إذا كان المجموع المتبقي صفرًا ، فهذا يعني أننا وصلنا إلى هدفنا المطلوب. عند هذه النقطة ، ندفع القائمة المؤقتة الحالية للأعداد الصحيحة إلى مصفوفة الإخراج من المصفوفات.

انظر أيضا
مشكلة تغيير العملة

رمز  

كود C ++ لـ Combination Sum Leetcode Solution

#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 Solution

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 هي العنصر الأدنى بين جميع العناصر المرشحة الأخرى.