સબસેટ લીટકોડ  


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એમેઝોન સફરજન બ્લૂમબર્ગ ByteDance ફેસબુક Google માઈક્રોસોફ્ટ ઓરેકલ
ગાણિતીક નિયમો અરે બેકટ્રેકીંગ બીટ બિટ મેનિપ્યુલેશન બિટ્સ કોડિંગ મુલાકાત ઇન્ટરવ્યુની તૈયારી લેટકોડ LeetCodeSolutions

સબસેટ લીટકોડ સમસ્યામાં આપણે અલગ પૂર્ણાંકો, નંબરોનો સમૂહ આપ્યો છે, બધા સબસેટ્સ (પાવર સેટ) છાપો.

નૉૅધ: સોલ્યુશન સેટમાં ડુપ્લિકેટ સબસેટ્સ હોવા જોઈએ નહીં.

એરે એ એ એરે બીનો સબસેટ છે જો કેટલાક (સંભવત,, શૂન્ય અથવા બધા) તત્વોને કા byીને બીમાંથી મેળવી શકાય છે.

ઉદાહરણ  

ઇનપુટ:

[1, 2, 3]

આઉટપુટ:

[1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]

અભિગમ 1: બીટ મેનીપ્યુલેશનનો ઉપયોગ કરીને ઇટરેટિવ સોલ્યુશન  

N તત્વોના સમૂહના દરેક સબસેટને n બિટ્સના ક્રમ તરીકે રજૂ કરી શકાય છે, જે 0… 2n-1 વચ્ચે પૂર્ણાંકને અનુરૂપ છે. બીટ સિક્વન્સમાંના મુદ્દાઓ સૂચવે છે કે સબસેટમાં કયા ઘટકો શામેલ છે.

અલ્ગોરિધમ

  1. જાહેર કરો એક એરે વેક્ટર “એન્સ” ના જેમાં આપણે આપણા બધા સબસેટ્સ સંગ્રહિત કરીશું.
  2. એક ચલ n પ્રારંભ કરો જે nums_array નું કદ રજૂ કરે છે.
  3. હું 0 થી 2 ની રેન્જમાં લૂપ ચલાવોn-1
    1. એરે "ટેમ્પ્" પ્રારંભ કરો જેમાં આપણે આપણું વર્તમાન સબસેટ સંગ્રહિત કરીશું.
    2. 0 થી n-1 ની રેન્જમાં j માટે લૂપ ચલાવો
      1. જો હુંનો jth બીટ સેટ કરેલો છે, તો પછી ટેમ્પર એરેમાં નંબર્સ [i] ને ઉમેરો.
    3. “ટેમ્પ” એરે ને “એન્સ” માં ઉમેરો
  4. અંતિમ અન્સ એરે છાપો.
આ પણ જુઓ
એરે લીટકોડ સોલ્યુશનમાં અદ્રશ્ય થઈ ગયેલા તમામ નંબર્સ શોધો

બધી સબસેટ્સને છાપવા માટેના અમલીકરણ

#include <bits/stdc++.h>
using namespace std;
int main()
{
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> ans;
    for (int i = 0; i < (1 << (nums.size())); i++)
    {
        vector<int> temp;
        for (int j = 0; j < nums.size(); j++)
        {
            if (i & (1 << j))
            {
                temp.push_back(nums[j]);
            }
        }
        ans.push_back(temp);
    }
    for (auto x : ans)
    {
        if(x.size()>0)
        cout<<"[";
        for (auto y : x)
        {
            if(y==x[x.size()-1])
            cout << y <<"]";
            else
            cout << y <<", "; 
        }
        cout << endl;
    }
    return 0;
}
[1]
[2]
[1, 2]
[3]
[1, 3]
[2, 3]
[1, 2, 3]

બધી સબસેટ્સને છાપવા માટે જટિલતા વિશ્લેષણ

સમયની જટિલતા

અમે બે નેસ્ટેડ લૂપ્સ ચલાવીએ છીએ, એક રેન્જ 2. N અને બીજો રેન્જ એન. તેથી અંતિમ સમયની જટિલતા ઓ (2 ^ n * n) છે.

જગ્યાની જટિલતા

ત્યાં 2 ^ n-1 સબસિટો છે અને દરેક સબસેટ માટે, અમને સરેરાશ ઓ (એન) જગ્યાની જરૂર હોય છે તેથી કુલ જગ્યા જટિલતા ઓ (2 ^ n * n) છે.

શું આપણે તેને optimપ્ટિમાઇઝ કરી શકીએ?

હા, અમે બેકટ્રેકીંગનો ઉપયોગ કરીને તેને optimપ્ટિમાઇઝ કરી શકીએ, ચાલો જોઈએ કે કેવી રીતે!

અભિગમ 2: બેકટ્રેકીંગનો ઉપયોગ કરીને રિકરિવ સોલ્યુશન  

આપણે નંબર્સ એરે ઉપર ફેરવીએ છીએ અને દરેક પોઝિશન માટે આપણી પાસે બે પસંદગી છે, કાં તો આઈથ એલિમેન્ટ લો અથવા તેને અવગણો.

અલ્ગોરિધમ

  1. ફંક્શન બનાવો જે દલીલો, અંતિમ જવાબ એરે, વર્તમાન સબસેટ એરે, ઇનપુટ એરે અને વેરીએબલ "અનુક્રમણિકા" લે છે જે નંબર્સ એરેમાં હાલના તત્વને નિર્દેશ કરે છે.
  2. બેઝ શરત: જો "અનુક્રમણિકા" નંબર્સ એરેના કદની બરાબર છે, તો પછી અમારી વર્તમાન સબસેટ એરેને અંતિમ જવાબમાં ઉમેરો કારણ કે હવે આપણે હવે nums એરેને પસાર કરી શકતા નથી.
  3. અમારી પાસે હવે બે પસંદગીઓ છે
    1. વર્તમાન તત્વ છોડો અને અનુક્રમણિકા + 1 સાથે રિકરિવ ફંક્શનને ક callલ કરો અને અન્ય તમામ દલીલો સમાન રહેશે.
    2. વર્તમાન સબસેટમાં વર્તમાન તત્વ ઉમેરો અને અનુક્રમણિકા +1 અને અન્ય દલીલો સાથે રિકરિવ ફંક્શનને ક callલ કરો. રિકરિવ ફંક્શનને બોલાવ્યા પછી, વર્તમાન સબસેટમાંથી છેલ્લા ઘટકને દૂર કરીને બેકટ્રેકિંગ પગલું કરો.
  4. અંતિમ જવાબ છાપો.
આ પણ જુઓ
સિક્કાઓની મહત્તમ સંખ્યા તમે લીટકોડ સોલ્યુશન મેળવી શકો છો

ઉદાહરણ સાથે સમજો

ચાલો ઇનપુટ એરે નંબર્સ લઈએ = [1,2,3]

પછી રિકર્ઝન ટ્રી આના જેવો દેખાશે:

સબસેટ લીટકોડપિન

ઉપરોક્ત ઝાડમાં, સબસેટ (i) એ રિકરિવ ફંક્શન છે જ્યાં હું વર્તમાન અનુક્રમણિકા સૂચવે છે.

બધી સબસેટ્સને છાપવા માટેના અમલીકરણ

સબસેટ લીટકોડ માટે સી ++ પ્રોગ્રામ

#include <bits/stdc++.h>
using namespace std;
void subsets(vector<vector<int>> &ans, vector<int> &temp, vector<int> &nums, int i)
{
    if (i == nums.size())
    {
        ans.push_back(temp);
        return;
    }
    subsets(ans, temp, nums, i + 1);
    temp.push_back(nums[i]);
    subsets(ans, temp, nums, i + 1);
    temp.pop_back();
    return;
}
int main()
{
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> ans;
    vector<int> temp;
    subsets(ans, temp, nums, 0);
    for (auto x : ans)
    {
        if(x.size()>0)
        cout<<"[";
        for (auto y : x)
        {
            if(y==x[x.size()-1])
            cout << y <<"]";
            else
            cout << y <<", "; 
        }
        cout << endl;
    }
    return 0;
}
[3]
[2]
[2, 3]
[1]
[1, 3]
[1, 2]
[1, 2, 3]

સબસેટ લીટકોડ માટે જાવા પ્રોગ્રામ

import java.util.*; 
public class Main
{
    static List<List<Integer>> res;
    public static void subsets(int[] nums,int index,List<Integer> list){
        if(index==nums.length-1){
            res.add(new ArrayList<Integer>(list));
            list.add(nums[index]);
            res.add(new ArrayList<Integer>(list));
            list.remove(list.size()-1);
            return;
        }
        subsets(nums,index+1,list);
        list.add(nums[index]);
        subsets(nums,index+1,list);
        list.remove(list.size()-1);
    }
  public static void main(String[] args) {
      res = new ArrayList<>();
      int[] nums={2, 3, 4};
      List<Integer> list = new ArrayList<Integer>();
      subsets(nums, 0, list);
      for(List<Integer> subset:res){
          for(int i: subset){
              System.out.print(i+", ");
          }
            System.out.println();
      }
  }
}

4, 
3, 
3, 4, 
2, 
2, 4, 
2, 3, 
2, 3, 4, 

સબસેટ લીટકોડ માટે જટિલતા વિશ્લેષણ

સમયની જટિલતા

દરેક અનુક્રમણિકા માટે, અમે 2 રિકર્ઝન ક callsલ્સ કરીએ છીએ અને ત્યાં n તત્વો છે તેથી કુલ સમય જટિલતા ઓ (2 ^ n) છે.

જગ્યાની જટિલતા

ત્યાં 2 ^ n-1 સબસિટો છે અને દરેક સબસેટ માટે, અમને સરેરાશ ઓ (એન) જગ્યાની જરૂર હોય છે તેથી કુલ જગ્યા જટિલતા ઓ (2 ^ n * n) છે.

સંદર્ભ