সমস্যাঃ একটি সেট দেওয়া আছে, সেই সেটের সকল সাবসেট তৈরি করার ফাংশন লিখতে হবে।
সমাধানঃ ইন্টারভিউতে এই প্রশ্ন করা হলে শুরুতেই দুটি বিষয় পরিষ্কার হয়ে নিতে হবে। সেটি হচ্ছে, ফাঁকা সেট এবং ওই সেটটি নিজে তার সাবসেট কী না। আমাদের এই আলোচনায়, দুটি উত্তরই হচ্ছে, হ্যাঁ।
সমাধান দেখার আগে নিজে চেষ্টা করা উচিত। এখানে গিয়ে সমস্যা দেখা যাবে ও সমাধান জমা দেওয়া যাবে – https://leetcode.com/problems/subsets/
তাহলে, ইনপুট যদি হয় [1, 2, 3], আউটপুট হবে, [[], [1], [2], [3], [1, 2], [2, 3], [1, 3], [1, 2, 3]]। আউটপুট লিস্টের উপাদানগুলোর ক্রম ভিন্ন হলেও সমস্যা নেই, কিন্তু একই জিনিস দুইবার থাকতে পারবে না।
আমরা রিকার্শন ব্যবহার করে খুব সহজেই সমস্যাটির সমাধান করতে পারি। আমরা প্রতিবার সেট থেকে একটি উপাদান নেওয়ার চেষ্টা করব। তবে আমাদেরকে খেয়াল রাখতে হবে যেন, একই উপাদান একাধিকবার নেওয়া না হয়। সেজন্য একটি বুলিয়ান অ্যারে বা লিস্ট ব্যবহার করতে পারি (visited)। বিস্তারিত ব্যাখ্যা না করে, বরং কোড লিখে দিচ্ছি। তবে কোড বুঝার জন্য খাতা-কলম নিয়ে বসতে হবে। আর যারা ডিএফএস (dfs)-এর সঙ্গে পরিচিত, তারা সহজেই বুঝতে পারবে। আর যারা পরিচিত নও, তাদেরও খুব একটা সমস্যা হবে না।
def subsets1(S):
if S == []:
return [[]]
result = [[]]
n = len(S)
visited = [False] * n
def recurse(i, n, li):
if i == n:
return
if len(li) > 0:
result.append([x for x in li])
for j in range(i, n):
if visited[j]:
continue
visited[j] = True
li.append(S[j])
recurse(j, n, li)
li.pop()
visited[j] = False
recurse(0, n, [])
return result
এখন কথা হচ্ছে, ইন্টারভিউতে সমাধান করাই শেষ কথা নয়। কেউ এই কোড লেখা পরে ইন্টারভিউয়ার যদি বলেন, এবারে রিকার্শন ছাড়া সমাধান করে দেখান, তখন রিকার্শন ছাড়া সমাধান করতে হবে। যেসব সমস্যা রিকার্শন ব্যবহার করে সহজে করা যায়, সেগুলো রিকার্শন ছাড়া সমাধান করতে গেলে স্ট্যাক ব্যবহারের প্রয়োজন হতে পারে। আবার না বুঝে কোড লিখলেও হবে না। কারণ ইন্টারভিউতে পুরো কোড ব্যাখ্যাও করতে হবে। সুতরাং ভালো প্রস্তুতির প্রয়োজন।
সম্পূর্ণ কোড এখানে – https://gist.github.com/tamim/87d3b79ff15d3375a98e9e0cd73b7c73