ప్రస్తారణలు లీట్‌కోడ్ పరిష్కారం  


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది Adobe అమెజాన్ ఆపిల్ Atlassian బ్లూమ్బెర్గ్ ByteDance eBay <span style="font-family: Mandali; ">ఫేస్‌బుక్ </span> Garena GoDaddy గోల్డ్మన్ సాచ్స్ గూగుల్ లింక్డ్ఇన్ మైక్రోసాఫ్ట్ ఒరాకిల్ అమ్మకాల బలం SAP ఉబెర్ VMware వాల్‌మార్ట్ ల్యాబ్స్ యాహూ
అల్గోరిథంలు బ్యాక్‌ట్రాకింగ్ కోడింగ్ ఇంటర్వ్యూ ఇంటర్వ్యూ ప్రిపరేషన్ లీట్‌కోడ్ LeetCodeSolutions

సమస్య ప్రస్తారణల లీట్‌కోడ్ సొల్యూషన్ పూర్ణాంకాల యొక్క సరళమైన క్రమాన్ని అందిస్తుంది మరియు పూర్తి వెక్టర్‌ను తిరిగి ఇవ్వమని అడుగుతుంది లేదా అమరిక ఇచ్చిన క్రమం యొక్క అన్ని ప్రస్తారణలలో. కాబట్టి, సమస్యను పరిష్కరించే ముందు. ప్రస్తారణల గురించి మనకు తెలిసి ఉండాలి. కాబట్టి, ప్రస్తారణ అనేది ఇచ్చిన పూర్ణాంకాల అమరిక తప్ప మరొకటి కాదు. కాబట్టి, మనకు ఒక క్రమం యొక్క అన్ని ప్రస్తారణలు అవసరమని చెప్పినప్పుడు. మేము ఇచ్చిన క్రమం యొక్క అన్ని ఏర్పాట్లను ముద్రించాల్సిన అవసరం ఉంది. మంచి అవగాహన కోసం కొన్ని ఉదాహరణలను పరిశీలిద్దాం.

Given sequence: [1,2,3]
Permutations: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

వివరణ: మీరు 1, 2, 3 ను ఒక క్రమంలో వ్రాయగల అన్ని మార్గాలు అవుట్‌పుట్‌గా ఇవ్వబడ్డాయి. ప్రస్తారణలో 6, 1, 2 వ్రాయడానికి మొత్తం 3 మార్గాలు ఉన్నాయి.

[0,1]
[[0,1],[1,0]]

వివరణ: 2, 0 వ్రాయడానికి 1 మార్గాలు మాత్రమే ఉన్నాయి.

ప్రస్తారణల లీట్‌కోడ్ పరిష్కారం కోసం బ్యాక్‌ట్రాకింగ్ అప్రోచ్  

ప్రస్తారణలు లీట్‌కోడ్ పరిష్కారంపిన్

ప్రస్తారణల సమస్య లీట్‌కోడ్ సొల్యూషన్ ఇచ్చిన సీక్వెన్స్ యొక్క అన్ని ప్రస్తారణలను ఉత్పత్తి చేయమని కోరింది. సాధారణంగా, మేము ప్రస్తారణను ఉత్పత్తి చేయవలసి ఉంటుంది లేదా కొన్ని సీక్వెన్స్ రికర్షన్ వెళ్ళడానికి కీలకం. కానీ ఇక్కడ పునరావృతం లేదా బ్యాక్‌ట్రాకింగ్ కొంచెం గమ్మత్తైనది. ఎంపిక చేయని మూలకాల నుండి ఒక మూలకాన్ని ఎంచుకొని, సమాధానం చివరిలో ఉంచడం ఒక మార్గం. ఈ విధంగా ప్రస్తారణను ఉత్పత్తి చేస్తుంది మరియు ఈ ప్రస్తారణ ఉత్పత్తి చేయబడిందని మరియు పునరావృతం కాకూడదని గుర్తుంచుకోండి. కానీ దీన్ని చేయడానికి బదులుగా, మేము పనిని నిర్వహించడానికి సరళమైన మార్గాన్ని కనుగొనటానికి ప్రయత్నిస్తాము. మనం ఒక మూలకాన్ని ఎంచుకొని ప్రస్తుత మూలకంతో మార్చుకుంటే. ప్రస్తుత సూచిక తర్వాత సీక్వెన్స్ వన్ ఇండెక్స్ కోసం అన్ని ప్రస్తారణలను రూపొందించడానికి పునరావృత కాల్ చేయండి.

ఇది కూడ చూడు
రెండు క్రమబద్ధీకరించిన లింక్డ్ జాబితాలను విలీనం చేయండి

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

బ్యాక్‌ట్రాకింగ్ కోడ్  

ప్రస్తారణల లీట్‌కోడ్ పరిష్కారం కోసం సి ++ కోడ్

#include <bits/stdc++.h>
using namespace std;

void permutationUtil(vector<int> &nums, int i, int &numsSize, vector<vector<int>> &answer){
    if(i == numsSize){
        answer.push_back(nums);
    }
    for(int j = i; j < numsSize; j++){
        swap(nums[i], nums[j]);
        permutationUtil(nums, i+1, numsSize, answer);
        swap(nums[i], nums[j]);
    }
}

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> answer;
    int numsSize = nums.size();
    permutationUtil(nums, 0, numsSize, answer);
    return answer;
}

int main(){
    vector<int> nums({1, 2, 3});
    vector<vector<int>> answer = permute(nums);
    for(auto i: answer){
        for(auto j: i)
            cout<<j<<" ";
        cout<<"\t";
    }
}
1 2 3   1 3 2   2 1 3   2 3 1   3 2 1   3 1 2

ప్రస్తారణల లీట్‌కోడ్ పరిష్కారం కోసం జావా కోడ్

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main {
    public static void permutationUtil(List<Integer> nums, int i, int numsSize, List<List<Integer>> answer){
        if(i == numsSize){
            answer.add(new ArrayList<Integer>(nums));
        }
        for(int j = i; j < numsSize; j++){
            Collections.swap(nums, i, j);
            permutationUtil(nums, i+1, numsSize, answer);
            Collections.swap(nums, i, j);
        }
    }
 
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> answer = new LinkedList();
        int numsSize = nums.length;
        List<Integer> list = new ArrayList<Integer>();
        for(int i=0;i<numsSize;i++)
            list.add(nums[i]);
        permutationUtil(list, 0, numsSize, answer);
        return answer;
    }
 
    public static void main(String[] args){
    	int nums[] = {1, 2, 3};
    	List<List<Integer>> answer = permute(nums);
    	System.out.println(answer.toString());
    }
}
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]

సంక్లిష్టత విశ్లేషణ  

సమయం సంక్లిష్టత

ఓ (సిగ్మా (పి (ఎన్, కె)), ఇక్కడ P అనేది n లేదా పాక్షిక ప్రస్తారణ యొక్క k ప్రస్తారణ. మరింత అధికారికంగా, P (N, k) = (N!) / ((Nk)!).

ఇది కూడ చూడు
ఉప-శ్రేణుల లీట్‌కోడ్ పరిష్కారాన్ని తిప్పికొట్టడం ద్వారా రెండు శ్రేణులను సమానంగా చేయండి

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

పై!), మేము N అయిన అన్ని పరిష్కారాలను నిల్వ చేయాలి కాబట్టి! పరిమాణంలో N అనేది శ్రేణి యొక్క పరిమాణం.