FilesExpand file tree

 master

/

FactorCombination.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

66 lines (56 loc) · 1.28 KB

 master

/

FactorCombination.java

Copy path

Top

File metadata and controls

• Code
• Blame

66 lines (56 loc) · 1.28 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

63

64

65

66

/*Numbers can be regarded as product of its factors. For example,

8 = 2 x 2 x 2;

= 2 x 4.

Write a function that takes an integer n and return all possible combinations of its factors.

Note:

Each combination's factors must be sorted ascending, for example: The factors of 2 and 6 is [2, 6], not [6, 2].

You may assume that n is always positive.

Factors should be greater than 1 and less than n.

Examples:

input: 1

output:

[]

input: 37

output:

[]

input: 12

output:

[

[2, 6],

[2, 2, 3],

[3, 4]

]

input: 32

output:

[

[2, 16],

[2, 2, 8],

[2, 2, 2, 4],

[2, 2, 2, 2, 2],

[2, 4, 4],

[4, 8]

]*/

public class Solution {

public List<List<Integer>> getFactors(int n) {

}

}

public List<List<Integer>> getFactors(int n) {

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

helper(result, new ArrayList<Integer>(), n, 2);

return result;

}

public void helper(List<List<Integer>> result, List<Integer> item, int n, int start){

if (n <= 1) {

if (item.size() > 1) {

result.add(new ArrayList<Integer>(item));

}

return;

}

for (int i = start; i <= n; ++i) {

if (n % i == 0) {

item.add(i);

helper(result, item, n/i, i);

item.remove(item.size()-1);

}

}

}