گڏيل سم ليٽڪوڊ حل


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ ايڊوب Airbnb Amazon ايپل Atlassian Bloomberg ByteDance eBay ڪريو Goldman سيچ گوگل LinkedIn، Microsoft جي Oracle Snapchat چورس سليمان وساڻ VMware والارٽ ليبز
ڪيريو واپسي

مسئلو گڏيل ڪرڻ وارو سيم ليٽ ڪوڊ اسان کي فراهم ڪري ٿو صف يا انجيگرن جي فهرست ۽ هڪ ٽارگيٽ. اسان کي چيو ويو آهي ته گڏجاڻيون ڳوليون جيڪي انهن عددن کي ڪنهن به تعداد ۾ استعمال ڪري سگھجن ٿيون جيڪي حد تائين ڏنل حد تائين شامل هونديون آهن. تنهن ڪري وڌيڪ رسمي طور تي ، اسان ڏنل عددن کي ڪنهن به ڀيري استعمال ڪري سگهون ٿا. گهربل ٻاھر آھي اھڙا مجموعا جيڪي ڏنل ھدف جي برابر رقم آھن.

مثالگڏيل سم ليٽڪوڊ حل

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 ٻا sum ڏنل ڏنل حد تائين.

گڏيل سمت ليٽ ڪوڊ جو حل

مسئلي جو انداز ڳولڻ آسان آهي. عام طور تي ، مسئلن وانگر هي ، اسان کي گهربل موٽ ڏيڻ جي ضرورت آهي. ڇو ته اهڙن سوالن ۾ اسان کي مڪمل ڳولا ۽ جواب ڳولڻ جي ضرورت آهي. تنهنڪري پهرين ، اسان اڪثريت وارن جي فهرست ترتيب ڏيون ٿا جيڪي اسان کي ڏنل آهن. اڳتي هلي ، اسان هڪ ٻيهر ريورس فنڪشن ٺاهي ٿو جيڪو انٽيگرس جي هاڻوڪي عارضي لسٽ ۾ انٽيگرس کي شامل ڪندو رهي ٿو ۽ ڏنل ٽارگيٽ کي شامل ڪرڻ لاءِ باقي رقم کي رکڻ دوران ڌيان ڏيندو آهي. تنهنڪري تجديد واري فنڪشن جي اندر ، اسان ٻه بنيادي ڪيس رکون ٿا. پهريون بنياد ڪيس اهو چيڪ ڪرڻ آهي ته باقي رقم گهربل منفي وڃي ٿي. انهي صورت ۾ ، اسين بحالي واري فنڪشن کان واپس اينداسين. ٻيون بنيادي صورت اسان جي گهربل حالت آهي جيڪڏهن باقي رقم صفر جي برابر آهي. جيڪڏهن بچيل رقم صفر آهي ته هن جو مطلب آهي ته اسان پنهنجي گهربل حد تائين پهچي چڪا آهيون. انهي نقطي تي ، اسان ٻاھرين جي موجوده عارضي لسٽ کي تري جي آئوٽ جي قطار ۾ دٻايو ٿا.

ڪوڊ

مجموعو سم ليٽ ڪوڊ حل لاءِ سي ++ ڪوڊ

#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

جاوا ڪوڊ گڏيل سمٿ ليٽ ڪوڊ حل لاءِ

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

پيچيدگي تجزيي

وقت جي پيچيدگي

اي (اين ^ (ايم / ٽي + 1)) جتي اين اميدوارن جو تعداد آهي ، ايم سڀني ڏنل ساٿي جي وچ ۾ سڀني کان نن candidateو اميدوار آهي ، ۽ ٽي هدف وارو قدر آهي. اهڙيءَ ريت وقت جي پيچيدگي غير متوقع آهي ۽ اها توقع ڪئي وئي آهي ڇاڪاڻ ته الگورتھم ٻيهر صحيح نموني آهي.

خلائي پيچيدگي

اي (ٽي / ايم) ، جتي ٽي ٽارگيٽ ويليو آھي ۽ ايم ٻين سڀني اميدوارن جي وچ ۾ گھٽ ۾ گھٽ عنصر آھي