-1

For example I have array with length n=3:

for(int i = 0; i < n; i++) {
    array[i] = i;
}

So the cases should be:

1. 0
2. 1
3. 2
4. 0 1
5. 0 2
6. 1 2
7. 0 1 2

So the number of cases should be 7 for n = 3. In my code:

int n = 3;
int[] array = new int[n];
for (int i = 0; i < n; i++) {
    array[i] = i;
}
int sum = 0;

for (int i = 0; i < n; i++) {
    System.out.println(array[i] + " ");
    sum++;
    for (int j = i; j < n; j++) {
        System.out.print(array[j] + " ");
    }
    System.out.println();
    sum++;
}
System.out.println("sum = " + sum);

Output is: 

0 
0 1 2 
1 
1 2 
2 
2 
sum = 6

The number 2 is two times so it is wrong and sum is actually = 5. And I don't get cases 

4. 0 1 
and 
5. 0 2

How to count all possible cases?

Zabuzard
  • 25,064
  • 8
  • 58
  • 82
Marta Wiśniewska
  • 19
  • 2
  • 3
    Math.pow(2,n) - 1? – Anindya Dutta Dec 13 '17 at 01:12
  • 1
    Looks like a [power set](https://en.wikipedia.org/wiki/Power_set). – Robby Cornelissen Dec 13 '17 at 01:18
  • 1
    **Why the down-votes**? The question is **clear**, contains an **example**, **desired output** and the **current output**. Also OP **showed effort** by trying it first on her own and she's also showing us the code as [mcve]. Looks good to me. If she doesn't know the term "*power set*" the problem itself also is not that easy to solve. – Zabuzard Dec 13 '17 at 02:15

1 Answers1

1

Sets, not arrays

The first important observance is that you are not using fixed length arrays here but sets of different lengths.

Take a look at your example. You allow

0
1
2
0, 1
0, 2
1, 2

which are not all of size 3.

Also you don't differentiate between

0, 1
1, 0

so order doesn't matter, like in sets.

Power set

That's why you're actually describing power sets here. For the example set {0, 1, 2} its power set is defined as

P({0, 1, 2}) = {
    {}, // empty set
    {0},
    {1},
    {2},
    {0, 1},
    {0, 2},
    {1, 2},
    {0, 1, 2}
}

Fortunately there exists an easy closed formula for their size. If n is the size of the input set the size of the power set is

2^n

But they also count the empty set, so you will need to -1 if you don't want that:

2^n - 1

Solution

Thus in Java you could write

int Set<Integer> input = ...
int size = (int) Math.pow(2, input.size()) - 1;

and that's all, you don't need to build the contents manually.

But if you're curious and want to build them, take a look at questions like Obtaining a powerset of a set in Java. It's an implementation of the recursive formula shown at Wikipedia.

So, totally inefficient but also working:

int Set<Integer> input = ...

// Build the power-set using the method from linked question
Set<Set<Integer>> power = powerSet(input);

int size = power.size() - 1;
Zabuzard
  • 25,064
  • 8
  • 58
  • 82