leetcode

0 class Solution {

1 public:

2 bool canPartitionKSubsets(vector<int> &nums, int k) const {

3 int acc = 0;

4

5 for (const int n : nums)

6 acc += n;

7 if (acc % k) return false;

8

9 const int goal = acc / k;

10

11 sort(rbegin(nums), rend(nums));

12 if (nums[0] > goal) return false;

13

14 const function<bool(uint16_t, int, int, int)> rec = [&](uint16_t visited, int left, int sum,

15 int start) {

16 if (sum == goal) left--, sum = 0, start = 0;

17 if (left == 1) return true;

18

19 for (int i = start; i < size(nums); i++) {

20 const uint16_t mask = 1 << i;

21 if (visited & mask) continue;

22 if (sum + nums[i] > goal) continue;

23

24 if (rec(visited | mask, left, sum + nums[i], i + 1)) return true;

25 if (sum == 0) return false;

26 }

27

28 return false;

29 };

30

31 return rec(1, k, nums[0], 1);

32 }

33 };

34

35 class Solution {

36 public:

37 bool canPartitionKSubsets(vector<int> &nums, int k) const {

38 static int acc[16];

39 int sum = 0;

40

41 for (const int n : nums)

42 sum += n;

43 if (sum % k) return false;

44

45 const int goal = sum / k;

46

47 sort(rbegin(nums), rend(nums));

48 if (nums[0] > goal) return false;

49

50 memset(acc, 0x00, sizeof(acc));

51 acc[0] = nums[0];

52

53 function<bool(int)> rec = [&](int crnt) {

54 if (crnt == size(nums)) return true;

55

56 for (int i = 0; i < k; i++) {

57 if (acc[i] + nums[crnt] > goal) continue;

58

59 acc[i] += nums[crnt];

60 if (rec(crnt + 1)) return true;

61 acc[i] -= nums[crnt];

62

63 if (acc[i] == 0) return false;

64 }

65

66 return false;

67 };

68

69 return rec(1);

70 }

71 };