Simple Java Solution (Slight Modification to Permute Algo)


  • 0
    N

    Basic permutation algorithm with a simple change to maintain lexicographic order.

    Algo

    • list itemThe idea is to pick up 'ith' element and push all the elements to their right by one position to make room for it at 'begin' position.

    • list itempermue the array to its right

    • list itemRestore the original array (i.e pull back all elements to the left by one position to make room for nums[begin] at ith position)

    Please note that push and pull elements in the array will not change the overall time complexity since n < n!

    class Solution {
        public List<List<Integer>> permute(int[] nums) {
    		List<List<Integer>> list = new ArrayList<>();
    		permute(nums, 0, list);
    		return list;
    	}
            private List<Integer> getList(int[] a) {
    		List<Integer> list = new ArrayList<>();
    		for (int i : a) {
    			list.add(i);
    		}
    		return list;
    	}
    	public void permute(int[] a, int begin, List<List<Integer>> list) {
    		if (begin == a.length - 1) {
    			list.add(getList(a));
    			return;
    		}
    		for (int i = begin; i < a.length; i++) {
    			put_i_at_begin(a, begin, i);
    			permute(a, begin + 1, list);
    			restore(a, begin, i);
    		}
    	}
    
    	private void restore(int[] a, int i, int j) {
    		int tmp = a[i];
    		while (i < j) {
    			a[i] = a[i + 1];
    			i++;
    		}
    		a[j] = tmp;
    	}
    	private void put_i_at_begin(int[] a, int begin, int i) {
    		int tmp = a[i];
    		while (i > begin) {
    			a[i] = a[i - 1];
    			--i;
    		}
    		a[begin] = tmp;
    	}
    }
    

Log in to reply
 

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