FilesExpand file tree

 master

/

subsetsII.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

99 lines (92 loc) · 2.85 KB

 master

/

subsetsII.java

Copy path

Top

File metadata and controls

• Code
• Blame

99 lines (92 loc) · 2.85 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

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

// Source : https://oj.leetcode.com/problems/subsets-ii/

// Inspired by : http://www.jiuzhang.com/solutions/subsets-ii/

// Author : Lei Cao

// Date : 2015-10-02

/**********************************************************************************

*

* Given a collection of integers that might contain duplicates, S, return all possible subsets.

*

* Note:

*

* Elements in a subset must be in non-descending order.

* The solution set must not contain duplicate subsets.

*

* For example,

* If S = [1,2,2], a solution is:

*

* [

* [2],

* [1],

* [1,2,2],

* [2,2],

* [1,2],

* []

* ]

*

*

**********************************************************************************/

package subsets;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Collections;

import java.util.List;

public class subsetsII {

/**

* Leetcode version

* @param nums

* @return

*/

public List<List<Integer>> subsetsWithDup(int [] nums) {

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

if (nums == null || nums.length == 0) {

return result;

}

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

Arrays.sort(nums);

addSubset(result, list, nums, 0);

return result;

}

private void addSubset(List<List<Integer>> result, ArrayList<Integer> list, int[] nums, int pos) {

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

for (int i = pos; i < nums.length; i++) {

// in this level, if current loop is not the start element, check if it's duplicated with the previous element

if (i != pos && nums[i - 1] == nums[i]) {

continue;

}

list.add(nums[i]);

addSubset(result, list, nums, i + 1);

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

}

}

/**

* Lintcode version

* @param S: A set of numbers.

* @return: A list of lists. All valid subsets.

*/

public ArrayList<ArrayList<Integer>> subsetsWithDup(ArrayList<Integer> s) {

// write your code here

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

if (s == null || s.size() == 0) {

return result;

}

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

Collections.sort(s);

addSubset(s, result, list, 0);

return result;

}

private void addSubset(

ArrayList<Integer> s,

ArrayList<ArrayList<Integer>> result,

ArrayList<Integer> list,

int pos) {

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

for (int i = pos; i < s.size(); i++) {

if (i != pos && s.get(i - 1) == s.get(i)) {

continue;

}

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

addSubset(s, result, list, i + 1);

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

}

}

}