محلول ترکیبی از مجموع Leetcode


سطح دشواری متوسط
اغلب در خشت Airbnb آمازون سیب Atlassian بلومبرگ ByteDance ای بی فیس بوک گلدمن ساکس گوگل لینک مایکروسافت وحی Snapchat مربع حال بارگذاری آموزش VMware آزمایشگاه های والمارت
صف عقب نشینی

مسئله Combination Sum Leetcode Solution برای ما فراهم می کند صف یا لیستی از اعداد صحیح و یک هدف. به ما گفته می شود که ترکیبی را که می توان با استفاده از این عدد صحیح به تعداد دفعاتی که به هدف داده می شود ، پیدا کرد. بنابراین به صورت رسمی تر ، می توانیم از عدد صحیح داده شده هر چند بار استفاده کنیم به گونه ای که به هدف داده شده اضافه شود. خروجی مورد نیاز ترکیبی است که مجموع آن برابر با هدف داده شده باشد.

مثالمحلول ترکیبی از مجموع 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 تکرار می شود. ما می توانیم تأیید کنیم که هر 3 خروجی جمع شده به هدف داده شده است.

رویکرد برای راه حل ترکیبی ترکیبی

یافتن رویکرد برای این مسئله ساده است. به طور کلی ، در مشکلاتی از این قبیل ، ما ملزم به استفاده از عقب گرد هستیم. زیرا در چنین سوالاتی ما مجبور به جستجوی کامل و یافتن پاسخ هستیم. بنابراین ابتدا لیستی از اعداد صحیح را که به ما داده شده مرتب می کنیم. پس از آن ، ما یک تابع بازگشتی ایجاد می کنیم که به اضافه کردن یک عدد صحیح به لیست موقت فعلی اعداد صحیح و پیگیری مقدار باقیمانده مورد نیاز برای جمع کردن هدف مورد نظر ، ادامه می دهد. بنابراین در داخل تابع بازگشتی ، دو حالت پایه را حفظ می کنیم. اولین مورد اساسی این است که بررسی کنید آیا مقدار باقیمانده مورد نیاز منفی می شود یا خیر. در این صورت ، ما از تابع بازگشتی برمی گردیم. حالت مبنای دوم شرط مورد نیاز ماست اگر مجموع باقیمانده برابر با صفر باشد. اگر مبلغ باقیمانده صفر باشد ، این بدان معنی است که ما به هدف مورد نیاز خود رسیده ایم. در آن مرحله ، لیست موقت فعلی اعداد صحیح را به آرایه خروجی آرایه ها وارد می کنیم.

رمز

کد C ++ برای راه حل ترکیبی ترکیبی

#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

کد جاوا برای 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 عنصر حداقل در میان سایر نامزدها است.