FilesExpand file tree

 master

/

Subsets78.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

76 lines (61 loc) · 1.85 KB

 master

/

Subsets78.java

Copy path

Top

File metadata and controls

• Code
• Blame

76 lines (61 loc) · 1.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

/**

* Given a set of distinct integers, nums, return all possible subsets.

*

* Note: The solution set must not contain duplicate subsets.

*

* For example,

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

*

* [

* [3],

* [1],

* [2],

* [1,2,3],

* [1,3],

* [2,3],

* [1,2],

* []

* ]

*/

import java.util.ArrayList;

import java.util.Arrays;

import java.util.HashSet;

import java.util.List;

import java.util.Set;

public class Subsets78 {

/**

* https://discuss.leetcode.com/topic/46159/a-general-approach-to-backtracking-questions-in-java-subsets-permutations-combination-sum-palindrome-partitioning

*/

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

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

backtrack(list, new ArrayList<>(), nums, 0);

return list;

}

private void backtrack(List<List<Integer>> list , List<Integer> tempList, int [] nums, int start){

list.add(new ArrayList<>(tempList));

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

tempList.add(nums[i]);

backtrack(list, tempList, nums, i + 1);

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

}

}

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

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

if (nums == null) return res;

res.add(new ArrayList<Integer>());

for (Integer n: nums) {

int size = res.size();

for (int i=0; i<size; i++) {

List<Integer> newList = new ArrayList<Integer>(res.get(i));

newList.add(n);

res.add(newList);

}

}

return res;

}

public static void main(String[] args) {

Subsets78 ss = new Subsets78();

System.out.println(ss.subsets(new int[]{1, 2, 3, 4}));

System.out.println(ss.subsets(new int[]{1, 2, 3}));

}

}