# Java solution using a bit-vector

• The idea is to use a bit-vector to represent whether a particular no has been used up while computing a permutation - to avoid repetitions. The bit-vector conserves a lot of space and also offers a O(1) set membership check, much like a HashSet.

``````public class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
BitSet usedNos = new BitSet(nums.length);
List<Integer> solutionVector = new ArrayList<>();

permute(nums, 0, usedNos, solutionVector, result);

return result;
}

private void permute(int[] nums, int currIndex, BitSet usedNos, List<Integer> solutionVector, List<List<Integer>> result) {
if(isSolutionFound(nums, currIndex)) {
processSolution(solutionVector, result);
}

for(int i = 0; i < nums.length; i++) {
if(!usedNos.get(i)) {
makeMove(usedNos, i, nums[i], solutionVector);
permute(nums, currIndex + 1, usedNos, solutionVector, result);
undoMove(usedNos, i, solutionVector);
}
}
}

private boolean isSolutionFound(int[] nums, int currIndex) {
return currIndex == nums.length;
}

private void processSolution(List<Integer> solutionVector, List<List<Integer>> result) {
List<Integer> permutation = new ArrayList<>();
for(Integer choice : solutionVector) {
}
}

private void makeMove(BitSet usedNos, int choiceIndex, Integer choice, List<Integer> solutionVector) {
usedNos.set(choiceIndex);