CC-8 : Find all subsets of list of numbers.
Description:
Given an array of input numbers, find all subsets of the same.
Test cases and expected outputs:
| Input Parameters |
Expected outputs |
| Original Array : 1,2,3,4
|
1234
123
124
12
134
13
14
1
234
23
24
2
34
3
4
|
Pseudocode:
findSubsets(nums[]):
| The array named nums of numbers to be checked is received as input parameter.
|
| Define ArrayList allSubsets to hold list of all subsets found in nums.
|
| Define ArrayList subset to one subset found.
|
| Call findSubsetsDfs(nums, 0, allSubSets, subset).
|
| Return allSubsets.
|
findSubsetDfs(nums, idx,allSubsets,subset):
| If (idx=nums.length):
Add subset to allSubSets.
Return.
|
| Add nums[idx] to subset.
|
| Recursively call findSubsetDfs(nums,idx+1, allSubsets, subset).
|
| Remove last num from subset.
|
| Recursively call findSubsetDfs(nums,idx+1, allSubsets, subset).
|
Code:
public ArrayList<ArrayList<Integer>> findSubsets(int[] nums) {
ArrayList<ArrayList<Integer>> allSubsets=new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> subset = new ArrayList<>();
findSubsetsDfs(nums,0,allSubsets,subset);
return allSubsets;
}
private void findSubsetsDfs(int[] nums, int idx,
ArrayList<ArrayList<Integer>> allSubsets, ArrayList<Integer> subset) {
if (idx==nums.length) {
allSubsets.add(new ArrayList<Integer>(subset));
return;
}
subset.add(nums[idx]);
findSubsetsDfs(nums,idx+1,allSubsets,subset);
subset.remove(subset.size()-1);
findSubsetsDfs(nums,idx+1,allSubsets,subset);
}rn Math.max(arr[n-1], findMax(arr,n-1));
}
Click here to download and run code and test cases !
Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it.
Be sure to try your own test cases to enhance your understanding !
You can also tweak the code to optimize or add enhancements and custom features.
import java.util.ArrayList;
public class RecursionFindSubsets {
public ArrayList<ArrayList<Integer>> findSubsets(int[] nums) {
ArrayList<ArrayList<Integer>> allSubsets=new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> subset = new ArrayList<>();
findSubsetsDfs(nums,0,allSubsets,subset);
return allSubsets;
}
private void findSubsetsDfs(int[] nums, int idx,
ArrayList<ArrayList<Integer>> allSubsets, ArrayList<Integer> subset) {
if (idx==nums.length) {
allSubsets.add(new ArrayList<Integer>(subset));
return;
}
subset.add(nums[idx]);
findSubsetsDfs(nums,idx+1,allSubsets,subset);
subset.remove(subset.size()-1);
findSubsetsDfs(nums,idx+1,allSubsets,subset);
}
public static void printArraySummary(int[] intArray, String label) throws Exception {
// Case 1: The input Array is null !!
if (intArray == null) { System.out.println("\n\n Input Array was null !! \n"); return; }
// Case 2: Print input Array by index (first to last)
System.out.println();
System.out.println("************************************************************************");
System.out.print(label+" : ");
int arrayIndex=0;
for (arrayIndex=0; arrayIndex < intArray.length; arrayIndex++) {
System.out.print(intArray[arrayIndex]);
if (arrayIndex < intArray.length-1) {System.out.print(",");}
}
System.out.println();
System.out.println(" ************************************************************************");
System.out.println();
Thread.sleep(2000);
return;
}
public static void main(String[] args) {
/***********************
Test cases given below
**********************/
ArrayList<ArrayList<Integer>> retVal;
try {
RecursionFindSubsets rcn=new RecursionFindSubsets();
int[] nums={1,2,3,4};
retVal=rcn.findSubsets(nums);
printArraySummary(nums, "Original Array");
for (int idx=0; idx < retVal.size(); idx++) {
System.out.println();
ArrayList<Integer> subset=retVal.get(idx);
for (int jdx=0; jdx < subset.size(); jdx++) {
System.out.print(subset.get(jdx));
}
}
}catch (Exception exception) {
System.out.print("Exception: "+ exception);
exception.printStackTrace();
}
}
}