LeetCode - Algorithms - 46. Permutations

just verify code of other peer.

Problem

46. Permutations

Given a collection of distinct integers, return all possible permutations.

Java

BASIC ALGORITHM 1: REMOVE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> permute(int[] nums) {
    	List<List<Integer>> list = new ArrayList<List<Integer>>();
    	permutation_remove(nums,nums.length,list);
    	return list;        
    }

	  private void permutation_remove(int[] a, int n, List<List<Integer>> list) {
  		if (n == 1) {
  			List<Integer> x = new ArrayList<Integer>();
  			for(int i=0;i<a.length;i++)
  				x.add(new Integer(a[i]));
  			list.add(x);
  			return;
  		}
  		for (int i = 0; i < n; i++) {
  			swap(a, i, n - 1);
  			permutation_remove(a, n - 1, list);
  			swap(a, i, n - 1);
  		}
	 }

   private void swap(int[] a, int i, int j) {
		int t = a[i];
		a[i] = a[j];
		a[j] = t;
	}
}

Submission Detail

  • 25 / 25 test cases passed.
  • Runtime: 1 ms, faster than 97.52% of Java online submissions for Permutations.
  • Memory Usage: 38 MB, less than 82.98% of Java online submissions for Permutations.

HEAP’S ALGORITHM

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> permute(int[] nums) {
    	List<List<Integer>> list = new ArrayList<List<Integer>>();
    	permutation_heaps(nums,nums.length,list);
    	return list;        
    }

	private void permutation_heaps(int[] a, int n, List<List<Integer>> list) {
		if (n == 1) {
			List<Integer> x = new ArrayList<Integer>();
			for(int i=0;i<a.length;i++)
				x.add(new Integer(a[i]));
			list.add(x);
			return;
		}
		for (int i = 0; i < (n - 1); i++) {
			permutation_heaps(a, n - 1, list);
			if (n % 2 == 0)
				swap(a, n - 1, i);
			else
				swap(a, n - 1, 0);
		}
		permutation_heaps(a, n - 1, list);
	}

  private void swap(int[] a, int i, int j) {
		int t = a[i];
		a[i] = a[j];
		a[j] = t;
	}
}

Submission Detail

  • 25 / 25 test cases passed.
  • Runtime: 1 ms, faster than 97.52% of Java online submissions for Permutations.
  • Memory Usage: 36.3 MB, less than 98.58% of Java online submissions for Permutations.

ref