FilesExpand file tree

 master

/

PartitionToKEqualSumSubsets698.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

107 lines (96 loc) · 3.27 KB

 master

/

PartitionToKEqualSumSubsets698.java

Copy path

Top

File metadata and controls

• Code
• Blame

107 lines (96 loc) · 3.27 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

100

101

102

103

104

105

106

107

/**

* Given an array of integers nums and a positive integer k, find whether it's

* possible to divide this array into k non-empty subsets whose sums are all

* equal.

*

* Example 1:

* Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4

* Output: True

* Explanation: It's possible to divide it into 4 subsets

* (5), (1, 4), (2,3), (2,3) with equal sums.

*

* Note:

* 1 <= k <= len(nums) <= 16.

* 0 < nums[i] < 10000.

*/

public class PartitionToKEqualSumSubsets698 {

public boolean canPartitionKSubsets(int[] nums, int k) {

int sum = 0;

int N = nums.length;

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

sum += nums[i];

}

if (sum % k != 0) return false;

int target = sum / k;

boolean[] visited = new boolean[N];

return valid(nums, visited, 0, 0, target, k, N);

}

private boolean valid(int[] nums, boolean[] visited, int start, int curr, int target, int k, int N) {

if (k == 1) return true;

if (curr == target) return valid(nums, visited, 0, 0, target, k-1, N);

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

if (visited[i]) continue;

visited[i] = true;

if (valid(nums, visited, i, curr + nums[i], target, k, N)) return true;

visited[i] = false;

}

return false;

}

/**

* https://leetcode.com/problems/partition-to-k-equal-sum-subsets/solution/

*/

public boolean canPartitionKSubsets2(int[] nums, int k) {

int N = nums.length;

Arrays.sort(nums);

int sum = Arrays.stream(nums).sum();

int target = sum / k;

if (sum % k > 0 || nums[N - 1] > target) return false;

boolean[] dp = new boolean[1 << N];

dp[0] = true;

int[] total = new int[1 << N];

for (int state = 0; state < (1 << N); state++) {

if (!dp[state]) continue;

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

int future = state | (1 << i);

if (state != future && !dp[future]) {

if (nums[i] <= target - (total[state] % target)) {

dp[future] = true;

total[future] = total[state] + nums[i];

} else {

break;

}

}

}

}

return dp[(1 << N) - 1];

}

/**

* https://leetcode.com/problems/partition-to-k-equal-sum-subsets/solution/

*/

public boolean search(int[] groups, int row, int[] nums, int target) {

if (row < 0) return true;

int v = nums[row--];

for (int i = 0; i < groups.length; i++) {

if (groups[i] + v <= target) {

groups[i] += v;

if (search(groups, row, nums, target)) return true;

groups[i] -= v;

}

if (groups[i] == 0) break;

}

return false;

}

public boolean canPartitionKSubsets3(int[] nums, int k) {

int sum = Arrays.stream(nums).sum();

if (sum % k > 0) return false;

int target = sum / k;

Arrays.sort(nums);

int row = nums.length - 1;

if (nums[row] > target) return false;

while (row >= 0 && nums[row] == target) {

row--;

k--;

}

return search(new int[k], row, nums, target);

}

}