Simple recursion solution with explantion


  • 0

    This problem need the permutations in lexicographic order, here is the recursion method. When n is 4, we list out the result.

    1234 2134 3124 4123

    1243 2143 3142 4132

    1324 2314 3214 4213

    1342 2341 3241 4231

    1423 2413 3412 4312

    1432 2431 3421 4321

    The first column is the permutation begin with 1. For n elements permutation, the last permutation begin with 1 is 1n(n-1)...432. We swap the minimum among n(n-1)...432 with first number, that is swap the last one(here is 2) with first number, we get 2n(n-1)...431. Then reverse the last n - 1 number, we get 2134...(n-1)n, this is first permutation begin with 2. Now we enter the second column.

    The second column is the permutation begin with 2. The last permutation begin with 2 is 2n(n-1)...431, we swap the minimum among n(n-1)...431 with first number, but because 1 is the first number before, so we swap the second last one (here is 3) with first number, we get 3n(n-1)...421. Then reverse the last n - 1 number, we get 312...(n-1)n, this is the first permutation begin with 3. Now we enter the third column.

    The third column is the permutation begin with 3. The last permutation begin with 3 is 3n(n-1)...421, we swap the minimum among n(n-1)...421 with first number, but because 1 and 2 are the first number before, so we swap the third second last one(here is 4) with first number, we get 4n(n-1)...321. Then reverse the last n - 1 number, we get 412...(n-1)n, this is the first permutation begin with 4. Now we enter the fourth column.

    So we get a recursion solution.

    step 1: i = n

    step 2: get the permutations of last n -1 number recursion

    step 3: swap the nth number with the first number

    step 4: i--

    step 5: reverse the last n - 1 number

    step 6: go to step 2

    The terminal condition is i is the first number.

    Notice:
    At the end, we need reverse the array to ensure not change the array.

    public static List<List<Integer>> permute(int[] nums) {
    	List<List<Integer>> result = new ArrayList<List<Integer>>();
    	if (nums.length == 0)
    		return result;
    	permute(nums, 0, result);
    	reverse(nums, 0, nums.length - 1); //after permutation, we need to reverse array
    	return result;
    }
    public static void swap(int[] nums, int i, int j) {
    	int temp = nums[i];
    	nums[i] = nums[j];
    	nums[j] = temp;
    }
    public static void reverse(int[] nums, int begin, int end) {
    	while (begin < end) {
    		swap(nums, begin, end);
    		begin++;
    		end--;
    	}
    }
    private static void permute(int[] nums, int start, List<List<Integer>> result) {
    	if (start == nums.length - 1) {
    		List<Integer> temp = new ArrayList<Integer>();
    		for (int i = 0; i < nums.length; i++) {
    			temp.add(nums[i]);
    		}
    		result.add(temp);
    		return;
    	}
    	int i = nums.length;
    	while (i > start) {
    		permute(nums, start + 1, result);
    		swap(nums, start, i - 1);
    		i--;
    		if (i <= start)
    			break;
    		reverse(nums, start + 1, nums.length - 1);	
    	}
    }

Log in to reply
 

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