مجموعہ سم لیٹ کوڈ حل  


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے ایڈوب Airbnb ایمیزون ایپل اٹلی بلومبرگ ByteDance ای بے فیس بک گولڈمین سیکس گوگل لنکڈ مائیکروسافٹ اوریکل Snapchat چوک Uber VMware والمارٹ لیبز
یلگوردمز لڑی پس منظر کوڈنگ انٹرویو انٹرویو کی تیاری لیٹ کوڈ LeetCodeSolutions۔

مسئلہ مجموعہ لیٹ کوڈ حل ہمیں ایک فراہم کرتا ہے صف یا عدد کی فہرست اور ایک ہدف۔ ہمیں بتایا گیا ہے کہ وہ مجموعے تلاش کریں جو ان ٹیکرز کا استعمال کرتے ہوئے بنائے جاسکتے ہیں جو متعدد مرتبہ دیئے گئے ہدف میں شامل ہوجاتے ہیں۔ مزید باضابطہ طور پر ، ہم دیئے گئے عدد کو متعدد بار استعمال کرسکتے ہیں جس میں وہ دیئے گئے ہدف میں اضافہ کرتے ہیں۔ مطلوبہ آؤٹ پٹ وہ مجموعہ ہوتا ہے جس میں دیئے گئے ہدف کے برابر رقم ہوتی ہے۔

مثال کے طور پرمجموعہ سم لیٹ کوڈ حل  

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 آؤٹ پٹ ملتے ہیں۔

مجموعہ سم لیٹ کوڈ حل کے ل Appro اپروچ  

مسئلے کا نقطہ نظر تلاش کرنا آسان ہے۔ عام طور پر ، اس طرح کے مسائل میں ، ہمیں بیک ٹریکنگ استعمال کرنے کی ضرورت ہوتی ہے۔ کیونکہ ایسے سوالوں میں ہمیں ایک مکمل تلاشی لینے اور جواب تلاش کرنے کی ضرورت ہے۔ تو پہلے ، ہم انٹیجرز کی فہرست کو ترتیب دیتے ہیں جو ہمیں دیا جاتا ہے۔ اس کے بعد ، ہم ایک بار بار چلنے والی تقریب تشکیل دیتے ہیں جو موجودہ عارضی فہرست کی عدد میں اعدادوشمار کا اضافہ کرتا ہے اور دیئے گئے ہدف میں شامل کرنے کے لئے درکار بقیہ رقم کا ٹریک کرتا رہتا ہے۔ تو پنراورتی تقریب کے اندر ، ہم دو بیس کیس رکھتے ہیں۔ پہلے بیس کیس میں یہ چیک کرنا ہے کہ آیا مطلوبہ بقیہ رقم منفی ہے؟ اس صورت میں ، ہم بار بار چلنے والی تقریب سے واپس آئیں گے۔ دوسرا بیس کیس ہماری مطلوبہ حالت ہے اگر باقی رقم صفر کے برابر ہو۔ اگر باقی رقم صفر ہے تو اس کا مطلب یہ ہے کہ ہم اپنے مطلوبہ ہدف تک پہنچ گئے ہیں۔ اس وقت ، ہم موجودہ عارضی فہرست کو اشاروں کی آؤٹ پٹ سرنی میں دھکیلتے ہیں۔

یہ بھی دیکھتے ہیں
سکے کی تبدیلی کا مسئلہ

ضابطے  

مجموعہ سم لیٹ کوڈ حل کے لئے 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

مجموعہ سم لیٹ کوڈ حل کے لئے جاوا کوڈ

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) ، جہاں ٹی ہدف کی قیمت ہے اور M دوسرے تمام امیدواروں میں کم سے کم عنصر ہے۔