सबसेट लेकेटकोड


कठिनाई स्तर मध्यम
में अक्सर पूछा वीरांगना सेब ब्लूमबर्ग ByteDance Facebook गूगल माइक्रोसॉफ्ट ओरेकल
ऐरे बैक ट्रैकिंग बिट बिट मैनिपुलेशन बिट्स

सबसेट लेटकोड समस्या में हमने अलग पूर्णांक, अंक, सभी उपसेट (पावर सेट) प्रिंट किया है।

नोट: समाधान सेट में डुप्लीकेट सबसेट नहीं होना चाहिए।

एक सरणी A, सरणी B का एक उपसमूह है यदि कुछ (संभवतः, शून्य या सभी) तत्वों को हटाकर B से प्राप्त किया जा सकता है।

उदाहरण

इनपुट:

[1, 2, 3]

आउटपुट:

[१], [२], [१, २], [३], [१, ३], [२, ३], [१, २, ३]

दृष्टिकोण 1: बिट हेरफेर का उपयोग करके Iterative समाधान

N तत्वों के एक सेट के प्रत्येक सबसेट को n बिट्स के अनुक्रम के रूप में दर्शाया जा सकता है, जो 0… 2n-1 के बीच पूर्णांक से मेल खाता है। बिट अनुक्रम में जो इंगित करते हैं कि कौन से तत्व सबसेट में शामिल हैं।

कलन विधि

  1. डिक्लेयर ए सरणी वैक्टर "एन्स" जिसमें हम अपने सभी सबसेट को स्टोर करेंगे।
  2. एक वैरिएबल n को प्रारंभ करें जो संख्या के आकार को दर्शाता है।
  3. 0 से 2 की रेंज में I के लिए एक लूप चलाएंn-1
    1. एक सरणी "अस्थायी" को प्रारंभ करें, जिसमें हम अपने वर्तमान सबसेट को संग्रहीत करेंगे।
    2. J के लिए 0 से n-1 तक के लिए एक लूप चलाएँ
      1. यदि I का jth बिट सेट है, तो टेंप [i] को टेम्प अरेंज में जोड़ें।
    3. "Ans" में "अस्थायी" सरणी जोड़ें
  4. अंतिम ans ऐरे को प्रिंट करें।

प्रिंट सब सब्सक्रिप्शन के लिए कार्यान्वयन

#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 में से एक एन और रेंज एन के दूसरे। इसलिए अंतिम समय जटिलता हे (2 ^ n * n) है।

अंतरिक्ष की जटिलता

2 ^ n-1 सबसेट हैं और हर सबसेट के लिए हमें O (n) स्पेस की जरूरत है, इसलिए कुल स्पेस जटिलता O (2 ^ n * n) है।

क्या हम इसे अनुकूलित कर सकते हैं?

हाँ, हम इसे backtrack का उपयोग करके अनुकूलित कर सकते हैं, आइए देखें कि कैसे!

दृष्टिकोण 2: पुनरावर्ती का उपयोग करके पुनरावर्ती समाधान

हम अंक सरणी पर पुनरावृत्ति करते हैं और प्रत्येक स्थिति के लिए हमारे पास दो विकल्प होते हैं, या तो ith तत्व लेते हैं या इसे छोड़ते हैं।

कलन विधि

  1. एक फ़ंक्शन बनाएं जो तर्कों, अंतिम उत्तर सरणी, वर्तमान सबसेट सरणी, इनपुट सरणी, और एक चर "सूचकांक" लेता है जो अंक तत्व में वर्तमान तत्व को इंगित करता है।
  2. आधार स्थिति: यदि "सूचकांक" अंक सरणी के आकार के बराबर है, तो अंतिम उत्तर के लिए हमारे वर्तमान सबसेट सरणी को जोड़ दें क्योंकि अब हम अंकों के सरणी को अब और नहीं रोक सकते हैं।
  3. अभी हमारे पास दो विकल्प हैं
    1. वर्तमान तत्व को छोड़ दें और इंडेक्सिव फ़ंक्शन को इंडेक्स + 1 के साथ कॉल करें और अन्य सभी तर्क समान रहेंगे।
    2. वर्तमान तत्व को वर्तमान सबसेट में जोड़ें और पुनरावर्ती फ़ंक्शन को अनुक्रमणिका +1 और अन्य तर्कों के साथ कॉल करें। पुनरावर्ती फ़ंक्शन को कॉल करने के बाद, वर्तमान उपसमुच्चय से अंतिम तत्व को हटाकर पीछे के चरण को करें।
  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 पुनरावृत्ति कॉल करते हैं और n तत्व हैं इसलिए कुल समय जटिलता O (2 ^ n) है।

अंतरिक्ष की जटिलता

2 ^ n-1 सबसेट हैं और हर सबसेट के लिए हमें O (n) स्पेस की जरूरत है, इसलिए कुल स्पेस जटिलता O (2 ^ n * n) है।

संदर्भ