diff options
Diffstat (limited to 'sum_subset_xor.c')
-rw-r--r-- | sum_subset_xor.c | 23 |
1 files changed, 4 insertions, 19 deletions
diff --git a/sum_subset_xor.c b/sum_subset_xor.c index cb51647..7c32618 100644 --- a/sum_subset_xor.c +++ b/sum_subset_xor.c @@ -8,26 +8,11 @@ * if 'a' can be obtained from 'b' by deleting some elements of 'b'. */ -void backtrack(int *nums, int numsSize, int tar, int idx, int *cnt) { - if (idx == numsSize) { - return; - } else { - for (int i = idx; i < numsSize; i++) { - tar ^= nums[i]; - *cnt += tar; - backtrack(nums, numsSize, tar, i + 1, cnt); - tar ^= nums[i]; - } - } -} - int subsetXORSum(int *nums, int numsSize) { - int ans = 0; - for (int i = 0; i < numsSize; i++) { - ans += nums[i]; - backtrack(nums, numsSize, nums[i], i + 1, &ans); - } - return ans; + int all = 0, mult = 1 << (numsSize - 1); + for (int i = 0; i < numsSize; i++) + all |= nums[i]; + return all * mult; } int main() { |