Firstly the recursion tree:
n options on 1st layer, n - 1 options on 2nd layer ...
So, the recursion tree has (n!) nodes.
Then, in every recursion node:
we did a traverse on original array to check whether we can take the element or not.
This takes O(n)
And, every time we check an element:
We uses List.contains(), this method cost O(n) too.
So, totally the time complexity should be:
O(n * n * n!) = O(n^3)
If we use a boolean array
boolean used, we can avoid using List.contains() and make this step to O(1), so the total time will be:
O(n * n!) = O(n^2)
Are these correct???