కాంబినేషన్ సమ్ లీట్‌కోడ్ సొల్యూషన్  


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది Adobe airbnb అమెజాన్ ఆపిల్ Atlassian బ్లూమ్బెర్గ్ ByteDance eBay <span style="font-family: Mandali; ">ఫేస్‌బుక్ </span> గోల్డ్మన్ సాచ్స్ గూగుల్ లింక్డ్ఇన్ మైక్రోసాఫ్ట్ ఒరాకిల్ Snapchat స్క్వేర్ ఉబెర్ 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 అవుట్‌పుట్‌లు ఇచ్చిన లక్ష్యానికి సమానం అని మేము ధృవీకరించవచ్చు.

కాంబినేషన్ సమ్ లీట్‌కోడ్ సొల్యూషన్ కోసం అప్రోచ్  

సమస్యకు సంబంధించిన విధానం కనుగొనడం చాలా సులభం. సాధారణంగా, ఇలాంటి సమస్యలలో, మేము బ్యాక్‌ట్రాకింగ్‌ను ఉపయోగించాల్సి ఉంటుంది. ఎందుకంటే ఇలాంటి ప్రశ్నలలో మనం పూర్తి శోధన చేసి సమాధానం కనుగొనవలసి ఉంటుంది. కాబట్టి మొదట, మనకు ఇవ్వబడిన పూర్ణాంకాల జాబితాను క్రమబద్ధీకరిస్తాము. తరువాత, మేము పునరావృత ఫంక్షన్‌ను సృష్టిస్తాము, ఇది ప్రస్తుత తాత్కాలిక పూర్ణాంకాల జాబితాకు పూర్ణాంకాన్ని జోడించడం మరియు ఇచ్చిన లక్ష్యాన్ని జోడించడానికి అవసరమైన మిగిలిన మొత్తాన్ని ట్రాక్ చేయడం. కాబట్టి పునరావృత ఫంక్షన్ లోపల, మేము రెండు బేస్ కేసులను ఉంచుతాము. మొదటి బేస్ కేసు అవసరమైన మొత్తం ప్రతికూలంగా ఉందో లేదో తనిఖీ చేయడం. అలాంటప్పుడు, మేము పునరావృత ఫంక్షన్ నుండి తిరిగి వస్తాము. మిగిలిన మొత్తం సున్నాకి సమానం అయితే రెండవ బేస్ కేసు మనకు అవసరమైన పరిస్థితి. మిగిలిన మొత్తం సున్నా అయితే దీని అర్థం మనం అవసరమైన లక్ష్యాన్ని చేరుకున్నాం. ఆ సమయంలో, మేము పూర్ణాంకాల యొక్క ప్రస్తుత తాత్కాలిక జాబితాను శ్రేణుల అవుట్పుట్ శ్రేణిలోకి నెట్టివేస్తాము.

ఇది కూడ చూడు
నాణెం మార్పు సమస్య

కోడ్  

కాంబినేషన్ సమ్ లీట్‌కోడ్ సొల్యూషన్ కోసం సి ++ కోడ్

#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 లక్ష్యం విలువ. అందువల్ల సమయం సంక్లిష్టత ఘాతాంకం మరియు అల్గోరిథం పునరావృత బ్యాక్‌ట్రాకింగ్ ఎందుకంటే ఇది expected హించబడింది.

అంతరిక్ష సంక్లిష్టత

O (T / M), ఇక్కడ T అనేది లక్ష్య విలువ మరియు అన్ని ఇతర అభ్యర్థులలో M కనీస మూలకం.

1