FilesExpand file tree

 master

/

Permutations.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

62 lines (55 loc) · 1.84 KB

 master

/

Permutations.java

Copy path

Top

File metadata and controls

• Code
• Blame

62 lines (55 loc) · 1.84 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

/**

* Practiced on 12/17/2012

*

* Given a collection of numbers, return all possible permutations.

*

* For example,

* [1,2,3] have the following permutations:

* [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

*

* =============================

* The following implementation does not use recursion, but it keeps building

* and deleting arraylists. Thus I believe it's slower.

*

* For another implementation that does not have this problem, but use recursion,

* check "PermutationsAnotherImplementation.java".

*/

package com.congli.leetcode;

import java.util.ArrayList;

public class Permutations {

public ArrayList<ArrayList<Integer>> permute(int[] num)

{

ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

if(num == null || num.length == 0) return null;

ArrayList<Integer> listInitial = new ArrayList<Integer>();

listInitial.add(num[0]);

result.add(listInitial);

for(int i = 1; i < num.length; ++i)

{

ArrayList<ArrayList<Integer>> newResult = new ArrayList<ArrayList<Integer>>();

for(ArrayList<Integer> list : result)

{

for(int j = 0; j <= list.size(); ++j)

{

ArrayList<Integer> newList = new ArrayList<Integer>();

getNewList(list, num[i], j, newList);

newResult.add(newList);

}

}

result = newResult;

}

return result;

}

private void getNewList(ArrayList<Integer> list, int num, int j, ArrayList<Integer> newList)

{

for(int i = 0; i < j; ++i)

{

newList.add(list.get(i));

}

newList.add(num);

for(int i = j; i < list.size(); ++i)

{

newList.add(list.get(i));

}

}

}