Java solution using a bit-vector


  • 0

    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) {
                permutation.add(choice);
            }
            result.add(permutation);
        }
        
        private void makeMove(BitSet usedNos, int choiceIndex, Integer choice, List<Integer> solutionVector) {
            usedNos.set(choiceIndex);
            solutionVector.add(choice);
        }
        
        private void undoMove(BitSet usedNos, int choiceIndex, List<Integer> solutionVector) {
            usedNos.clear(choiceIndex);
            solutionVector.remove(solutionVector.size() - 1);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.