Skip to main content

Find all distinct subsets of a given set

Here given code implementation process.

import java.util.HashSet;
/*
    Java Program for
    Find all distinct subsets of a given set
*/
public class Subsets
{
	public void allDistinctSubset(int[] arr, int n)
	{
		// This is used to collect unique subset
		HashSet < String > record = new HashSet < String > ();
		// Get value of 2ⁿ
		int size = (int) Math.pow(2, n);
		String subset = "";
		// Outer loop
		for (int i = 0; i < size; ++i)
		{
			// Inner loop are executing from 0...n-1
			for (int j = 0; j < n; ++j)
			{
				if ((i & (1 << j)) != 0)
				{
					subset += arr[j] + " ";
					// Add subset
					record.add(subset);
				}
			}
			subset = "";
		}
		// Display distinct subsets
		for (String result: record)
		{
			System.out.print("\n  " + result);
		}
	}
	public static void main(String[] args)
	{
		Subsets task = new Subsets();
		int[] arr = {
			1 , 2 , 2 , 3
		};
		// Get the size of array
		int n = arr.length;
		// Test
		task.allDistinctSubset(arr, n);
	}
}

Output

  2 2 3
  1 2 2 3
  1 3
  1 2
  2 2
  1 2 2
  2 3
  3
  1 2 3
  2
  1
// Include header file
#include <iostream>
#include <set>
#include <math.h>

using namespace std;
/*
    C++ Program for
    Find all distinct subsets of a given set
*/
class Subsets
{
	public: void allDistinctSubset(int arr[], int n)
	{
		// This is used to collect unique subset
		set < string > record;
		// Get value of 2ⁿ
		int size = (int) pow(2, n);
		string subset = "";
		// Outer loop
		for (int i = 0; i < size; ++i)
		{
			// Inner loop are executing from 0...n-1
			for (int j = 0; j < n; ++j)
			{
				if ((i &(1 << j)) != 0)
				{
					subset += to_string(arr[j])  +  " ";
					// Add subset
					record.insert(subset);
				}
			}
			subset = "";
		}
		// Display distinct subsets
		for (auto result : record)
		{
			cout << "\n  " << result;
		}
	}
};
int main()
{
	Subsets *task = new Subsets();
	int arr[] = {
		1 , 2 , 2 , 3
	};
	// Get the size of array
	int n = sizeof(arr) / sizeof(arr[0]);
	// Test
	task->allDistinctSubset(arr, n);
	return 0;
}

Output

  1
  1 2
  1 2 2
  1 2 2 3
  1 2 3
  1 3
  2
  2 2
  2 2 3
  2 3
  3
// Include namespace system
using System;
using System.Collections.Generic;
/*
    Csharp Program for
    Find all distinct subsets of a given set
*/
public class Subsets
{
	public void allDistinctSubset(int[] arr, int n)
	{
		// This is used to collect unique subset
		HashSet < string > record = new HashSet < string > ();
		// Get value of 2ⁿ
		int size = (int) Math.Pow(2, n);
		String subset = "";
		// Outer loop
		for (int i = 0; i < size; ++i)
		{
			// Inner loop are executing from 0...n-1
			for (int j = 0; j < n; ++j)
			{
				if ((i & (1 << j)) != 0)
				{
					subset += arr[j] + " ";
					// Add subset
					record.Add(subset);
				}
			}
			subset = "";
		}
		// Display distinct subsets
		foreach(String result in record)
		{
			Console.Write("\n  " + result);
		}
	}
	public static void Main(String[] args)
	{
		Subsets task = new Subsets();
		int[] arr = {
			1 , 2 , 2 , 3
		};
		// Get the size of array
		int n = arr.Length;
		// Test
		task.allDistinctSubset(arr, n);
	}
}

Output

  1
  2
  1 2
  2 2
  1 2 2
  3
  1 3
  2 3
  1 2 3
  2 2 3
  1 2 2 3
package main
import "strconv"
import "math"
import "fmt"
/*
    Go Program for
    Find all distinct subsets of a given set
*/

func allDistinctSubset(arr[] int, n int) {
	// This is used to collect unique subset
	var record = make(map[string] bool)
	// Get value of 2ⁿ
	var size int = int (math.Pow(2, float64(n)))
	var subset string = ""
	// Outer loop
	for i := 0 ; i < size ; i++ {
		// Inner loop are executing from 0...n-1
		for j := 0 ; j < n ; j++ {
			if (i & (1 << j)) != 0 {
				subset += strconv.Itoa(arr[j]) + " "
				// Add subset
				record[subset] = true
			}
		}
		subset = ""
	}
	// Display distinct subsets
	for v := range record {
		fmt.Print("\n  ", v)
	}
}
func main() {

	var arr = [] int { 1, 2, 2, 3 }
	// Get the size of array
	var n int = len(arr)
	// Test
	allDistinctSubset(arr, n)
}

Output

  2 
  2 2 
  1 3 
  2 3 
  1 2 3 
  2 2 3 
  1 
  1 2 
  1 2 2 
  3 
  1 2 2 3
<?php
/*
    Php Program for
    Find all distinct subsets of a given set
*/
class Subsets
{
    public  function allDistinctSubset($arr, $n)
    {
        // This is used to collect unique subset
        $record = array();
        // Get value of 2ⁿ
        $size = (int) pow(2, $n);
        $subset = "";
        // Outer loop
        for ($i = 0; $i < $size; ++$i)
        {
            // Inner loop are executing from 0...n-1
            for ($j = 0; $j < $n; ++$j)
            {
                if (($i & (1 << $j)) != 0)
                {
                    $subset .= strval($arr[$j])." ";
                    // Add subset
                    if (!isset($record[$subset]))
                    {
                        $record[$subset] = 1;
                    }
                }
            }
            $subset = "";
        }
        // Display distinct subsets
        foreach($record as $key => $value)
        {
            echo("\n  ".$key);
        }
    }
}

function main()
{
    $task = new Subsets();
    $arr = array(1, 2, 2, 3);
    // Get the size of array
    $n = count($arr);
    // Test
    $task->allDistinctSubset($arr, $n);
}
main();

Output

  1
  2
  1 2
  2 2
  1 2 2
  3
  1 3
  2 3
  1 2 3
  2 2 3
  1 2 2 3
/*
    Node JS Program for
    Find all distinct subsets of a given set
*/
class Subsets
{
	allDistinctSubset(arr, n)
	{
		// This is used to collect unique subset
		var record = new Set();
		// Get value of 2ⁿ
		var size = parseInt(Math.pow(2, n));
		var subset = "";
		// Outer loop
		for (var i = 0; i < size; ++i)
		{
			// Inner loop are executing from 0...n-1
			for (var j = 0; j < n; ++j)
			{
				if ((i & (1 << j)) != 0)
				{
					subset += arr[j] + " ";
					// Add subset
					record.add(subset);
				}
			}
			subset = "";
		}
		// Display distinct subsets
		for (let result of record)
		{
			process.stdout.write("\n  " + result);
		}
	}
}

function main()
{
	var task = new Subsets();
	var arr = [1, 2, 2, 3];
	// Get the size of array
	var n = arr.length;
	// Test
	task.allDistinctSubset(arr, n);
}
main();

Output

  1
  2
  1 2
  2 2
  1 2 2
  3
  1 3
  2 3
  1 2 3
  2 2 3
  1 2 2 3
import math
#    Python 3 Program for
#    Find all distinct subsets of a given set
class Subsets :
	def allDistinctSubset(self, arr, n) :
		#  This is used to collect unique subset
		record = set()
		#  Get value of 2ⁿ
		size =  2 ** n
		subset = ""
		i = 0
		#  Outer loop
		while (i < size) :
			j = 0
			#  Inner loop are executing from 0...n-1
			while (j < n) :
				if ((i & (1 << j)) != 0) :
					subset += str(arr[j]) + " "
					#  Add subset
					record.add(subset)
				
				j += 1
			
			subset = ""
			i += 1
		
		for result in record :
			print("\n  ", result, end = "")
		
	

def main() :
	task = Subsets()
	arr = [1, 2, 2, 3]
	#  Get the size of list
	n = len(arr)
	#  Test
	task.allDistinctSubset(arr, n)

if __name__ == "__main__": main()

Output

   2 2 3
   3
   1 2 2 3
   1 2 3
   1 2
   2
   1 3
   2 3
   1 2 2
   2 2
   1
require 'set'
#    Ruby Program for
#    Find all distinct subsets of a given set
class Subsets 
	def allDistinctSubset(arr, n) 
		#  This is used to collect unique subset
		record = SortedSet.new()
		#  Get value of 2ⁿ
		size = 2 ** n
		subset = ""
		i = 0
		#  Outer loop
		while (i < size) 
			j = 0
			#  Inner loop are executing from 0...n-1
			while (j < n) 
				if ((i & (1 << j)) != 0) 
					subset += arr[j].to_s + " "
					#  Add subset
					record.add(subset)
				end

				j += 1
			end

			subset = ""
			i += 1
		end

		#  Display distinct subsets
        record.each do |result|
          print("\n  ", result)
        end

	end

end

def main() 
	task = Subsets.new()
	arr = [1, 2, 2, 3]
	#  Get the size of array
	n = arr.length
	#  Test
	task.allDistinctSubset(arr, n)
end

main()

Output

  1 
  1 2 
  1 2 2 
  1 2 2 3 
  1 2 3 
  1 3 
  2 
  2 2 
  2 2 3 
  2 3 
  3 
import scala.collection.mutable._;
/*
    Scala Program for
    Find all distinct subsets of a given set
*/
class Subsets()
{
	def allDistinctSubset(arr: Array[Int], n: Int): Unit = {
		// This is used to collect unique subset
		var record: Set[String] = Set();
		// Get value of 2ⁿ
		var size: Int = Math.pow(2, n).toInt;
		var subset: String = "";
		var i: Int = 0;
		// Outer loop
		while (i < size)
		{
			var j: Int = 0;
			// Inner loop are executing from 0...n-1
			while (j < n)
			{
				if ((i & (1 << j)) != 0)
				{
					subset += arr(j).toString() + " ";
					// Add subset
					record.add(subset);
				}
				j += 1;
			}
			subset = "";
			i += 1;
		}
		// Display distinct subsets
		for (result <- record)
		{
			print("\n  " + result);
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Subsets = new Subsets();
		var arr: Array[Int] = Array(1, 2, 2, 3);
		// Get the size of array
		var n: Int = arr.length;
		// Test
		task.allDistinctSubset(arr, n);
	}
}

Output

  1 2 2 3
  2 2 3
  1 3
  1 2
  2 2
  2 3
  1 2 2
  3
  1 2 3
  2
  1
import Foundation;
/*
    Swift 4 Program for
    Find all distinct subsets of a given set
*/
class Subsets
{
	func allDistinctSubset(_ arr: [Int], _ n: Int)
	{
		// This is used to collect unique subset
		var record = Set<String>()
		// Get value of 2ⁿ
		let size: Int = Int(pow(Double(2), Double(n)));
		var subset: String = "";
		var i: Int = 0;
		// Outer loop
		while (i < size)
		{
			var j: Int = 0;
			// Inner loop are executing from 0...n-1
			while (j < n)
			{
				if ((i & (1 << j))  != 0)
				{
					subset += String(arr[j]) + " ";
					// Add subset
					record.insert(subset);
				}
				j += 1;
			}
			subset = "";
			i += 1;
		}
		// Display distinct subsets
		for result in record
		{
			print("\n  ", result, terminator: "");
		}
	}
}
func main()
{
	let task: Subsets = Subsets();
	let arr: [Int] = [1, 2, 2, 3];
	// Get the size of array
	let n: Int = arr.count;
	// Test
	task.allDistinctSubset(arr, n);
}
main();

Output

   3
   2 2 3
   2
   2 2
   1
   1 2
   2 3
   1 2 2
   1 2 3
   1 3
   1 2 2 3
/*
    Kotlin Program for
    Find all distinct subsets of a given set
*/
class Subsets
{
	fun allDistinctSubset(arr: Array < Int > , n: Int): Unit
	{
		// This is used to collect unique subset
		val record : MutableSet <String> = mutableSetOf <String> ();
		// Get value of 2ⁿ
		val size: Int = Math.pow(2.0, n.toDouble()).toInt();
		var subset: String = "";
		var i: Int = 0;
		// Outer loop
		while (i < size)
		{
			var j: Int = 0;
			// Inner loop are executing from 0...n-1
			while (j < n)
			{
				if ((i and(1 shl j)) != 0)
				{
					subset += arr[j].toString() + " ";
					// Add subset
					record.add(subset);
				}
				j += 1;
			}
			subset = "";
			i += 1;
		}
		// Display distinct subsets
		for (result in record)
		{
			print("\n  " + result);
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Subsets = Subsets();
	val arr: Array < Int > = arrayOf(1, 2, 2, 3);
	// Get the size of array
	val n: Int = arr.count();
	// Test
	task.allDistinctSubset(arr, n);
}

Output

  1
  2
  1 2
  2 2
  1 2 2
  3
  1 3
  2 3
  1 2 3
  2 2 3
  1 2 2 3
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment